【链表】打卡8：复制含有随机指针结点的链表

前言

以专题的形式更新刷题贴，欢迎跟我一起学习刷题，相信我，你的坚持，绝对会有意想不到的收获。每道题会提供简单的解答，如果你有更优雅的做法，欢迎提供指点，谢谢。

【题目描述】

一种特殊的链表结点类描述如下：

class NodeRand{
	public int value; 
	public NodeRand next;
	public NodeRand rand;
	public NodeRand(int data){
		this.value = data;
	}
}

NodeRand类中的value是结点值，next指针和正常单链表中next指针的意义一样，都指向下一个结点，rand指针是NodeRand类中新增的指针，这个指针可能指向链表中的任意一个结点，也可能指向null。给定一个由NodeRand结点类型组成的无环单链表的头结点head，请实现一个函数完成这个链表中所有结构的复制，并返回复制的新链表的头结点。例如：链表1->2->3->null，假如1的rand指针指向3，2的rand指针指向null，3的rand指针指向1。复制后的链表应该也是这种结构，比如，1’->2’->3’->null，1’的rand指针指向3’，2’的rand指针指向null，3’的rand指针指向1’，最后返回1’。

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N)。

进阶：不使用额外的数据结构，只用有限几个变量，且在时间复杂度为 O(N)内完成原问题要实现的函数。

【难度】

尉：★★☆☆

解答

方法一：使用额外的存储空间

这道题的难点在于我们需要定位好随机指针，一个比较简单的解法就是把原结点与复制的结点关联起来，可以使用哈希表把他们关联起来。

首先把副结点全部创建出来，然后把原结点与对应的副结点用哈希表关联起来。关联的时候原结点作为key，副结点作为value。例如对于链表 1->2->3->null。创建副结点 1’, 2’, 3’。然后用哈希表关联起来：

key	value
NodeRand_1	NodeRand_1’
NodeRand_2	NodeRand_2’
NodeRand_3	NodeRand_3’

之后再把所有副结点连接成一个链表。在连接的时候，我们可以通过哈希表很容易找到对应的随机结点。

代码如下

//使用哈希表关联原结点与复制的结点
//时间复杂度为 O(n), 空间复杂度也为 O(n)
public static NodeRand copyListWithRand(NodeRand head){
    if(head == null){
        return head;
    }
    Map<NodeRand, NodeRand> map = new HashMap<NodeRand, NodeRand>();
    NodeRand cur = head;
    //首先创建全部副结点
    while(cur != null){
        map.put(cur, new NodeRand(cur.value));
        cur = cur.next;
    }
    //把副结点串起来
    cur = head;
    while(cur!=null){
        map.get(cur).next = map.get(cur.next);
        map.get(cur).rand = map.get(cur.rand);
        cur = cur.next;
    }
    return map.get(head);
}

这种方法的时间复杂度为 O(n), 空间复杂度也为 O(n)。

方法2

其实我们也可以不需要哈希表来辅助，也就是说，我们是可以做到空间复杂度为 O(1)的，我们可以把复制的副结点插入到原链表中去，这样也能把原结点与副结点进行关联，进而定位到随机结点。例如，对于链表 1->2->3->null。首先生成副结点 1’, 2’, 3’。然后把副结点插入到原结点的相邻位置，即把原链表变成 1->1’->2->2’->3->3’->null。

这样我们也可以在连接副结点的时候，找到相应的随机结点。例如 1 的随机结点是 3，则 1’ 的随机结点是 3’。显然，1结点的随机结点的下一个结点就是 1’的随机结点。具体代码如下：

//空间复杂度O(1)
public static NodeRand copyListWithRand2(NodeRand head){
    if(head == null){
        return head;
    }
    NodeRand cur = head;
    NodeRand next = null;
    //创建并插入结点
    while(cur!=null){
        next = cur.next;
        NodeRand copyNode = new NodeRand(cur.value);
        cur.next = copyNode;
        copyNode.next = next;
        cur = next;
    }
    //再把复制的结点取出来连接起来
    cur = head;
    next = null;
    while(cur != null){
        next = cur.next.next;//使用next托管原链表的下一个结点
        cur.next.next = next != null ? next.next : null;//注意空结点判断
        cur.next.rand = cur.rand != null ? cur.rand.next : null;
        cur = next;
    }
    return head.next;
}