LeetCode連接（https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/）

難度：中等
題目描述：請(qǐng)實(shí)現(xiàn) copyRandomList 函數(shù)，復(fù)制一個(gè)復(fù)雜鏈表。在復(fù)雜鏈表中，每個(gè)節(jié)點(diǎn)除了有一個(gè) next 指針指向下一個(gè)節(jié)點(diǎn)，還有一個(gè) random 指針指向鏈表中的任意節(jié)點(diǎn)或者 null。

示例：

示例圖

輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

結(jié)點(diǎn)結(jié)構(gòu)如下：

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

解題過程

[注：本方法主要使用遞歸，由于本人對(duì)于遞歸理解不是很好，本題是一個(gè)很好的鍛煉機(jī)會(huì)，其他方法參考：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/fu-za-lian-biao-de-fu-zhi-by-leetcode-so-9ik5/]

本題要求復(fù)制鏈表，可能乍一看沒有什么難處，但是此題比較大的難處在于random指針如何指向未生成的結(jié)點(diǎn)，
比如說我現(xiàn)在復(fù)制到第一個(gè)結(jié)點(diǎn)，但是第一個(gè)結(jié)點(diǎn)的random屬性是指向第3個(gè)結(jié)點(diǎn)的，那么此時(shí)如何才能不破壞生成順序的前提下，將復(fù)制后的結(jié)點(diǎn)指向random結(jié)點(diǎn)呢？（先作為一個(gè)思考）
首先考慮一個(gè)問題，如果不算random屬性的特殊性，則本題相當(dāng)于單鏈表的復(fù)制
那么簡單的單鏈表的復(fù)制怎么寫呢？簡單的實(shí)現(xiàn)方式如下所示：（遞歸方法）

     private ListNode recur(ListNode node){
             if (node == null) {
                 return null;
             }
             ListNode curr = new ListNode(node.val);
             curr.next = recur(node.next);
             return curr;
     }

我們首先要清楚，添加操作需要添加結(jié)點(diǎn)(curr)和添加位置前一個(gè)結(jié)點(diǎn)(prev)（因?yàn)樾枰膎ext指針，如prev.next=curr）
那我們可以利用遞歸的方法，在遞歸之前將所有結(jié)點(diǎn)都創(chuàng)建出來，這時(shí)候只需要考慮如何將每個(gè)結(jié)點(diǎn)next指針賦值給前一個(gè)就好了
比較好的方法就是在遞歸返回的過程中，將每一個(gè)新建結(jié)點(diǎn)都返回，這樣我們就得到每一次遞歸的curr結(jié)點(diǎn)和prev結(jié)點(diǎn)，
當(dāng)遞歸完成后，正好返回的結(jié)點(diǎn)也是我們需要的新鏈表的頭結(jié)點(diǎn)。

這是簡單的單鏈表的復(fù)制方法，現(xiàn)在我們回到題目中，就會(huì)發(fā)現(xiàn)此題和單鏈表相似，只要解決了random指針的指向就完成本題了
如果結(jié)點(diǎn)的復(fù)制可以正常的參考單鏈表的復(fù)制，random指針指向的結(jié)點(diǎn)可以使用一個(gè)HashMap進(jìn)行存儲(chǔ)
可以將舊鏈表的結(jié)點(diǎn)作為HashMap的key值，新鏈表的結(jié)點(diǎn)作為value值，
當(dāng)給random賦值的時(shí)候檢查舊鏈表的結(jié)點(diǎn)的random是否指向null，如果指向null則新鏈表的結(jié)點(diǎn)的random也指向null
如果不指向null，則需要尋找舊鏈表結(jié)點(diǎn)的random值在HashMap中的key，可以找到對(duì)應(yīng)新鏈表結(jié)點(diǎn)，將random值賦值即可。

public Node copyRandomList(Node head) {
    return recur(head);
}

private Map<Node,Node> map = new HashMap<>();
private Node recur(Node node){
    if (node == null){
        return null;
    }
    Node curr = new Node(node.val);
    map.put(node, curr);
    curr.next = recur(node.next);
    curr.random = node.random == null? null : map.get(node.random);
    return curr;
}