《力扣刷题计划》复制带随机指针的链表

每一个结点有三个属性：

 

链表的样子大概是这样： 

 

注意这里我们复制的结点是引用类型，即我们复制的不只是结点的地址，我们需要复制的是旧结点。

比如一个这样的原链表

我们的复制不是又生成一个和上面一模一样的链表出来，我们复制的是有着原来链表结构的新的链表 

新的链表的每个结点所对应的值可能和原来链表的值相同，但next和random的肯定是不同的（但所对应的关系是相同的）

 为了在新链表中持和原来链表中各个结点的对应关系，我们需要用Map来记录

比如上图中

 代码展示：

/*
// 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 {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Map<Node, Node> map = new HashMap<>(); // 如果用TreeMap里面放的元素一定是可比较的,只能用HashMap
        // 构建新旧结点的键值对关系，旧结点是Key,新结点是Value
        while (cur != null) {
            Node tmp = new Node(cur.val); // 构造新结点tmp,旧结点是cur
            map.put(cur, tmp);
            cur = cur.next;
        }
        cur = head;
        // 按旧链表的结点对应关系构建新的结点，注意我们是深拷贝——即非引用类型可以直接把值拷贝出来，但对于引用类型我们拷贝的不只是地址值，还有该引用所对应的结点
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head); // 我们要返回的是新结点的head---及key(head) 所对应的 value值是map.get(head)
    }
}