【leetcode hot 100 138】随机链表的复制

解决一：回溯 + 哈希表

本题要求我们对一个特殊的链表进行深拷贝。如果是普通链表，我们可以直接按照遍历的顺序创建链表节点。而本题中因为随机指针的存在，当我们拷贝节点时，「当前节点的随机指针指向的节点」可能还没创建，因此我们需要变换思路。一个可行方案是，我们利用回溯的方式，让每个节点的拷贝操作相互独立。对于当前节点，我们首先要进行拷贝，然后我们进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝，拷贝完成后将创建的新节点的指针返回，即可完成当前节点的两指针的赋值。

具体地，我们用哈希表记录每一个节点对应新节点的创建情况。遍历该链表的过程中，我们检查「当前节点的后继节点」和「当前节点的随机指针指向的节点」的创建情况。如果这两个节点中的任何一个节点的新节点没有被创建，我们都立刻递归地进行创建。当我们拷贝完成，回溯到当前层时，我们即可完成当前节点的指针赋值。注意一个节点可能被多个其他节点指向，因此我们可能递归地多次尝试拷贝某个节点，为了防止重复拷贝，我们需要首先检查当前节点是否被拷贝过，如果已经拷贝过，我们可以直接从哈希表中取出拷贝后的节点的指针并返回即可。

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

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

class Solution {
    // <旧的node,新的node>
    Map<Node,Node> newNodeMap = new HashMap<>(); 

    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }
        if(!newNodeMap.containsKey(head)){
            // 有旧node，但是没有新node
            Node newNode = new Node(head.val);   // 注意上述构造函数
            newNodeMap.put(head, newNode);  // 要放在两个copyRandomList之上，否则后面会连续创建最终导致栈溢出
            newNode.next = copyRandomList(head.next);
            newNode.random = copyRandomList(head.random);
        }
        // return newNode;不可以，这是一个临时变量
        return newNodeMap.get(head);
    }
}

注意：

• 要return newNodeMap.get(head);，不可以return newNode;，因为这是一个这是一个临时变量。
• newNodeMap.put(head, newNode);要放在两个copyRandomList之上，否则后面会连续创建最终导致栈溢出；且后面的复制是地址赋值，就算先put了也会影响已经put的元素