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

链接：https://www.nowcoder.com/questionTerminal/f836b2c43afc4b35ad6adc41ec941dba?f=discussion
来源：牛客网

我的思路：在随机指针关系建立上，通过循环找到两个链表的对应关系。优点：运行快，缺点：内存占用大

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null){
            return pHead;
        }

        RandomListNode deepcopy = new RandomListNode(pHead.label);
        RandomListNode pointerD = deepcopy;
        RandomListNode pointerP = pHead;

        // 第一遍先通过顺序指针将链表建立出来
        while(pointerP.next != null){
            RandomListNode temp = new RandomListNode(pointerP.next.label);
            pointerD.next = temp;
            pointerD = pointerD.next;
            pointerP = pointerP.next;
        }

        pointerD = deepcopy;
        pointerP = pHead;

        // 第二遍建立随机指针关系
        while(pointerP != null){
            if(pointerP.random == null){
                pointerP = pointerP.next;
                pointerD = pointerD.next;
                continue;
            }
            RandomListNode pointerP1 = pHead;
            RandomListNode pointerD1 = deepcopy;
            // 这里是通过遍历将原链表和新链表对应上，
            while(pointerP1 != pointerP.random){
                pointerP1 = pointerP1.next;
                pointerD1 = pointerD1.next;
            }

            pointerD.random = pointerD1;
            pointerP = pointerP.next;
            pointerD = pointerD.next;
        }

        return deepcopy;
    }
}

别人的思路（参考自https://blog.nowcoder.net/n/27e887ce682b4ec798fce79ffa3097b4）：
使用了map保存两个链表的对应关系，以此建立随机指针。优点：内存占用下，缺点运行速度慢点。

import java.util.HashMap;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode p = pHead;
        //第一次遍历 新建立节点
        while(p != null){
            RandomListNode newNode = new RandomListNode(p.label);
            map.put(p, newNode);
            p = p.next;
        }
        //第二次遍历 赋值映射关系
        p = pHead;
        while(p != null){
            RandomListNode node = map.get(p);
            node.next = (p.next == null)?null: map.get(p.next);
            node.random = (p.random == null)?null: map.get(p.random);
            p = p.next;
        }
        //最后的返回值
        return map.get(pHead);

    }
}