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

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。
下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。

示例1:
输入:{1,2,3,4,5,3,5,#,2,#}
输出:{1,2,3,4,5,3,5,#,2,#}

题目分析

题目为复杂链表的复制，与一般链表的复制不同的是，不止要确定next结点，还要确定random结点，因为random结点可能还没有创建，所以需要注意。
示例1分析：
首先将输入显示分为两段，前半部分{1,2,3,4,5}为ListNode，后半部分{3,5,#,2,#}是随机指针域表示。
前半部分{1,2,3,4,5}可以表示链表 ListNode:1->2->3->4->5
后半部分{3,5,#,2,#}分别的表示为
1的位置指向3，2的位置指向5，3的位置指向null，4的位置指向2，5的位置指向null
如下图:

解题思路

方法1：
1.random结点需要在所有链表结点创建后，才能赋值，所以最后处理random，先对应链表老结点，创建新的结点（next确定）；
2.使用map将老结点和新结点之间的对应关系保存下来；
3.使用map获取老结点的random结点对应的新结点，从而赋给新结点。
关键代码：

Node oldNode;
while(old!= null){
     Node newNode= new Node(oldNode.label);
     map.put(oldNode,newNode);
     // 遍历old链表，获得old和new结点之间的对应关系
}
newNode.random = map.get(oldNode.random); // oldNode的radom结点也是oldNode，它对应的newNode就是目标的random

方法2：
1.将原链表原地复制一份，确定复制的结点的next指向；
2.遍历链表，确定复制结点的random指向（因为复制的多一份，所以复制的random=原来结点的random.next）；
3.将链表拆分成两个，返回复制的那条；
过程如图所示：
1.将原链表原地复制一份

复制只是增加新的结点，结点random都为空，绿色标记为复制的结点

2.为复制结点赋random值
这里为了清晰看复制结点，省略了原结点的random指向；

3.拆分成两个链表，主要是修改链表的nextzhixian

代码实现

方法一：使用map来保存链表结点的random对象，先按照链表顺序复制结点，将next值确定；遍历第二遍的时候确定random值。

public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null) return pHead;
        // 1.map解法
        RandomListNode newHead = new RandomListNode(pHead.label);
        RandomListNode tmp = newHead;
        RandomListNode next = pHead.next;
        // map中key为head中的node，value为复制的node
        HashMap<randomlistnode,randomlistnode> map = new HashMap<>();
        map.put(pHead,newHead);
        while(next != null){
            RandomListNode tnext = new RandomListNode(next.label);
            map.put(next,tnext);
            tmp.next = tnext;
            next = next.next;
            tmp = tmp.next;
        }
        tmp = newHead;
        // 当所有的node创建完后，才能添加random值
        while(tmp != null){
            tmp.random = map.get(pHead.random);
            tmp = tmp.next;
            pHead = pHead.next;
        }
        return newHead;
}

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

方法二：原地解法，将链表的每个节点都复制一份，遍历链表确定random，最后拆分成两个链表。

// 2.原地解法
public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null) return pHead;
        // 1.将拷贝节点放到原节点后面，例如1->2->3这样的链表就变成了这样1->1'->2->2'->3->3'
        for (RandomListNode node = pHead, copy = null; node != null; node = node.next.next) {
            copy = new RandomListNode(node.label);
            copy.next = node.next;
            node.next = copy;
        }
        // 2.把拷贝节点的random指针安排上
        for (RandomListNode node = pHead; node != null; node = node.next.next) {
            if (node.random != null) {
                node.next.random = node.random.next;
            }
        }
        // 3.分离拷贝节点和原节点，变成1->2->3和1'->2'->3'两个链表，后者就是答案
        RandomListNode newHead = pHead.next;
        for (RandomListNode node = pHead, temp = null; node != null && node.next != null;) {
            temp = node.next;
            node.next = temp.next;
            node = temp;
        }
        return newHead;
}

此方法的时间复杂度为O(n),空间复杂度为O(1)。