要求：輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值帖鸦，以及兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)胚嘲，另一個(gè)特殊指針random指向一個(gè)隨機(jī)節(jié)點(diǎn)）作儿，請(qǐng)對(duì)此鏈表進(jìn)行深拷貝，并返回拷貝后的頭結(jié)點(diǎn)馋劈。（注意攻锰，輸出結(jié)果中請(qǐng)不要返回參數(shù)中的節(jié)點(diǎn)引用，否則判題程序會(huì)直接返回空）
思路：
淺拷貝只復(fù)制指向某個(gè)對(duì)象的指針妓雾，而不復(fù)制對(duì)象本身娶吞，新舊對(duì)象還是共享同一塊內(nèi)存。但深拷貝會(huì)另外創(chuàng)造一個(gè)一模一樣的對(duì)象械姻，新對(duì)象跟原對(duì)象不共享內(nèi)存妒蛇，修改新對(duì)象不會(huì)改到原對(duì)象。

方法一：使用哈希表。第一步仍然是將原始鏈表上的每個(gè)節(jié)點(diǎn) N復(fù)制為N',然后把這些創(chuàng)建出來(lái)的節(jié)點(diǎn)N’連接起來(lái)绣夺。同時(shí)我們把<N,N'>的配對(duì)信息放到一個(gè)HashMap<Node,Node> map中;第二步設(shè)置每個(gè)節(jié)點(diǎn)的random指針:如果在原始鏈表中節(jié)點(diǎn) N的random指針指向節(jié)點(diǎn) S,那么在復(fù)制鏈表中,對(duì)應(yīng)的 N'節(jié)點(diǎn)應(yīng)該指向 S'毫缆。由于有了哈希表，我們可以用O(1)的時(shí)間根據(jù)S找到S'乐导。使用空間換時(shí)間，以O(shè)(n)的空間消耗把時(shí)間復(fù)雜度由降到浸颓。

public class L36_Clone {
    // 使用哈希表的方法

    public RandomListNode Clone(RandomListNode head) {
        // 判斷邊界
        if(head==null)return null;
        // 創(chuàng)建一個(gè)哈希表
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        // 定位一個(gè)臨時(shí)結(jié)點(diǎn)p物臂，指向頭結(jié)點(diǎn)
        RandomListNode p = head;
        // 從頭到尾將復(fù)制結(jié)點(diǎn)
        while(p!=null){
            // 將<N，N'>的配對(duì)信息放到一個(gè)哈希表中产上。
            map.put(p, new RandomListNode(p.label));
            p = p.next;
        }
        p = head;
        // 從頭到尾連接結(jié)點(diǎn)的next和random
        while(p!=null){
            map.get(p).next = map.get(p.next);
            map.get(p).random = map.get(p.random);
            p = p.next;
        }
        return map.get(head);
    }
}

方法二:不使用輔助空間的情況下實(shí)現(xiàn)O(n)的時(shí)間效率棵磷。
1、第一步：依然是根據(jù)原始鏈表的每個(gè)節(jié)點(diǎn)N創(chuàng)建對(duì)應(yīng)的N'晋涣。不過(guò)是把N'鏈接在N的后面仪媒。
2、第二步：重新遍歷鏈表谢鹊，復(fù)制老結(jié)點(diǎn)的隨機(jī)指針給新結(jié)點(diǎn)
3算吩、第三步：拆分鏈表，將鏈表拆分為原鏈表和復(fù)制后的鏈表

    // 方法二：不使用輔助空間的情況下實(shí)現(xiàn)O(n)的時(shí)間效率佃扼。
    // 第一步：依然是根據(jù)原始鏈表的每個(gè)節(jié)點(diǎn)N創(chuàng)建對(duì)應(yīng)的N'偎巢。不過(guò)是把N'鏈接在N的后面。
    public void copy(RandomListNode head){
        RandomListNode p = head;
        while(p!=null){
            // 復(fù)制一個(gè)新的節(jié)點(diǎn)
            RandomListNode cloneNode = new RandomListNode(p.label);
            RandomListNode nextNode = p.next;
            // 將復(fù)制的新節(jié)點(diǎn)連接到原來(lái)節(jié)點(diǎn)后面
            p.next = cloneNode;
            cloneNode.next = nextNode;
            p=nextNode;
        }
    }

    // 第二步：重新遍歷鏈表兼耀，復(fù)制老結(jié)點(diǎn)的隨機(jī)指針給新結(jié)點(diǎn)
    public void randomDirect(RandomListNode head){
        RandomListNode p = head;
        // 從頭到尾遍歷
        while(p!=null){
            // 找到原來(lái)節(jié)點(diǎn)的隨機(jī)指針压昼，復(fù)制的結(jié)點(diǎn)同時(shí)操作
            p.next.random = p.random==null? null:p.random.next;
            p = p.next.next;
        }

    }
    // 第三步：拆分鏈表，將鏈表拆分為原鏈表和復(fù)制后的鏈表
    public RandomListNode reList(RandomListNode head){
        RandomListNode p = head;
        RandomListNode cloneHead = p.next;
        while(p!=null){
            RandomListNode cloneNode = p.next;
            p.next = cloneNode.next;
            cloneNode.next = cloneNode.next==null?null:cloneNode.next.next;
            p = p.next;
        }
        return cloneHead;
    }