复制含有随机指针的链表

复制含有随机指针的链表

题目：复制含有随机指针的链表

《程序员代码面试指南》第20题 P63 难度：尉★★☆☆

这题牛客上没有，当然我也没做出来。。

看书上一共有两种解法。

普通解法是使用HashMap结构，时间复杂度和额外空间复杂度都为O(N)

key依次存放的是原来的节点，如1、2、3……

value依次存放的对应的副本节点，1‘、2‘、3‘……

这样就可以通过get(key)直接访问到对应的副本节点。

步骤如下：

1. 从左到右遍历链表，对每个节点都复制生成对应的副本节点，放入map中；
2. 再次从左到右遍历链表，设置每个副本节点的next和rand指针。

代码如下（力扣题解）：

public Node copyRandomList(Node head) {
    if(head == null){
      	return null;
    }
    Node cur = head;
    HashMap map = new HashMap<>();
    while(cur!=null){
      	map.put(cur,new Node(cur.val));
      	cur = cur.next;
    }
    cur=head;
    while(cur!=null){
        map.get(cur).next=map.get(cur.next);
        map.get(cur).random=map.get(cur.random);
        cur=cur.next;
    }
    return map.get(head);
}

进阶解法则只使用有限的几个变量完成所有的功能，故额外空间复杂度为O(1)。

核心思路是在原链表中每个节点后复制一个副本节点。

如：原链表为1->2->3，复制完后链表为1->1'->2->2'->3->3'

这样也可以直接通过原节点.next直接访问到其副本节点。

在设置完每个副本节点的rand后，再将链表拆分出来即可（同时设置了每个副本节点的next）。

如：混合链表为1->1'->2->2'->3->3'，拆分后分为2个链表：1->2->3、1'->2'->3'。

最后将1'返回即可。

书上代码如下：

public static Node copyListWithRand2(Node head) {
    if (head == null) {
      	return null;
    }
    Node cur = head;
    Node next = null;
    // 复制并链接每一个节点
    while (cur != null) {
      next = cur.next;
        cur.next = new Node(cur.value);
        cur.next.next = next;
        cur = next;
    }
    cur = head;
    Node curCopy = null;
    // 设置复制节点的rand指针
    while (cur != null) {
        next = cur.next.next;
        curCopy = cur.next;
        curCopy.rand = cur.rand != null ? cur.rand.next : null;
        cur = next;
    }
    Node res = head.next;
    cur = head;
    // 拆分
    while (cur != null) {
        next = cur.next.next;
        curCopy = cur.next;
        cur.next = next;
        curCopy.next = next != null ? next.next : null;
        cur = next;
    }
    return res;
}

由此可见，两种解法的核心思想都是确定原节点与副本节点的对应关系。普通解法的get(原节点)、进阶解法的原节点.next，这2种方法都能访问到原节点的副本节点，这样就可以根据原节点的rand节点设置副本节点的rand节点了。