复杂链表的复制

题目
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路

1.HashMap

用HashMap<RandomListNode, RandomListNode>来保存原有的节点和新建节点的对应关系。再遍历一遍原链表，利用map找出对应的random节点，更新新链表的random值。

代码

/*
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 pHead)
    {
        if(pHead == null) return null;
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode p = pHead;
        map.put(null, null);
        
        while(p != null){
            RandomListNode temp = new RandomListNode(p.label);
            map.put(p, temp);
            p = p.next;
        }
        p = pHead;
        while(p != null){
            RandomListNode cur = map.get(p);
            RandomListNode next = map.get(p.next);
            RandomListNode random = map.get(p.random);
            cur.next = next;
            cur.random = random;
            p = p.next;
        }
        return map.get(pHead);
    }
}

2.构造法

思路
分3步：
1.复制节点
2.添加random指向
3.拆分链表
在原有链表的每个节点后面构造label相等的新的节点，再遍历一遍链表，查询原节点的random指向，更新新节点的random, 最后拆分该链表。

代码

/*
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 pHead)
    {
        if(pHead == null) return null;
        RandomListNode p = pHead;
        while(p != null){
            RandomListNode temp = new RandomListNode(p.label);
            RandomListNode pNext = p.next;
            temp.next = pNext;
            p.next = temp;
            p = pNext;
        }
        p = pHead;
        while(p != null){
            if(p.random != null){
                p.next.random = p.random.next;
            }
            p = p.next.next;
        }
        p = pHead;
        RandomListNode newHead = pHead.next;
        RandomListNode p1 = newHead;
        while(p != null){
            p.next = p.next.next;
            p = p.next;
            if(p1.next != null)
            p1.next = p1.next.next;
            p1 = p1.next;
            
        }
        return newHead;
        
    }
}