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

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

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) return null;
        // 先复制正常节点串联到每个正常节点后边
        RandomListNode node = pHead;
        while (node != null) {
            RandomListNode copy = new RandomListNode(node.label);
            copy.next = node.next;
            node.next = copy;
            node = copy.next;
        }
        // 再遍历随机节点指向
        node = pHead;
        while (node != null) {
            if (node.random != null) {
                // 刚才的复制节点指向正常节点中随机节点的下一个
                node.next.random = node.random.next;
            }
            node = node.next.next;
        }

        // 最后拆分串联
        node = pHead;
        RandomListNode root = pHead.next;
        RandomListNode tmp = root;
        while (node != null) {
            node.next = tmp.next;
            tmp.next = node.next == null ? null : node.next.next;
            node = node.next;
            tmp = tmp.next;
        }
        return root;
    }
}

解题思想：直接在之前的链表上复制，每⼀个节点都复制⼀个节点跟在后⾯，之后再复制 random 节点。都复制完成之后，将复制的新节点连接起来。