day85(8.13)

1. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

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

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

思路：

• 重点解决的random指针的指向问题。

• 遍历链表可以完成next指向，但是如何让原链表中的random指针对应的指向位置和新链表的节点对应上就是需要解决的点。

• 这里利用到了Hash的Key|Value对应的特性。

• 将原链表节点与新链表节点进行对应。
• 这样就可以通过原链表的random指针找到原链表的对应节点，然后通过hash找到对应的value（也就是新链表中的与之对应的节点）。
• 这里hash表对应关系在遍历链表构建next指针中完成。

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node res = new Node(0);
        Node temp = res;
        Node cur = head;
        // 遍历链表，完成新链表中next指针构建以及hash表对应关系构建（旧链表节点|新链表节点）
        while(cur!=null){
            Node newNode = new Node(cur.val);
            map.put(cur,newNode);
            temp.next = newNode;
            temp = temp.next;
            cur = cur.next;
        }
        cur = head;
        temp = res.next;
        while(temp!=null){
            temp.random = map.get(cur.random);
            temp = temp.next;
            cur = cur.next;
        }
        return res.next;
    }
}