题解 | #复杂链表的复制#

方法一：用map来做是思路最简单的。
1.首先根据原链表，复制一份一模一样的链表节点存到map中。其中键为原链表的节点，值为复制后的节点。
2.根据原链表的指向关系，去构建map中复制链表节点的结构。

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
import java.util.*;
public class Solution {
    public RandomListNode Clone(RandomListNode head) {
         if (head == null) return null;

        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode cur = head;
        while (cur != null){
            map.put(cur,new RandomListNode(cur.label));
            cur = cur.next;
        }
        cur = head;//重新从头开始
        while (cur != null){
            //在map中获取原链表当前节点的下一节点的复制节点，挂到复制链表的当前节点下
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);//和上同理
            cur = cur.next;
        }
        return map.get(head);
    }
}

方法二：在原链表的基础上构建映射关系。空间复杂度小。
1.先复制每个节点，创建next映射关系，然后在搭建复制节点的random映射关系；
2.将原链表与复制链表的next关系分离开来。

/*
public class Node {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode head) {
         if (head == null) return null;
        RandomListNode cur = head;
        RandomListNode next = null;
        //复制节点，并将复制后的节点挂到原节点的后面
        // 1--->2
        // 1--->1'--->2
        while (cur != null){
            next = cur.next; //先将原来的cur的下一节点保存起来
            cur.next = new RandomListNode(cur.label);
            cur.next.next = next;
            cur = next;
        }
        //
        cur = head;//从头开始构建映射关系（复制后节点random的指向关系）
        RandomListNode curCopy = null; //表示当前节点的复制节点
        while (cur != null){
            next = cur.next.next;
            curCopy = cur.next;
            curCopy.random = cur.random != null ? cur.random.next:null;
            cur = next;
        }
        //进行分离操作random上的指针不需要再改动了，只需要将next指针进行分离即可。
        RandomListNode resHead = head.next;//保存最后需要返回的头节点（就是原头节点后的复制节点）
        cur = head;
        while (cur != null){
            next = cur.next;//保存当前节点的下一个节点（即复制节点）
            cur.next = next.next; //让复制节点的下一个节点（即原节点的下一个节点）挂在当前节点下（恢复原来的位置）
            next.next = next.next != null ? next.next.next:null;//若复制节点的下一节点不为空（那么一定有下一个复制节点），将其挂在前一个复制节点后
            cur = cur.next; // 后移cur
        }
        return resHead;
    }
}