138：复制带随机指针的链表

问题描述

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的 深拷贝。

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

示例

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

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

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

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

提示：
-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。

思路

设置一个Hashmap即可。 先遍历一遍复制正常的链表。再利用HashMap更新random指针。（方法一）
也可以复制链表，直接把新结点接在旧结点的后面。然后更新random结点。然后把两个链表拆分即可。（方法二）

方法一

class Solution {
    HashMap<Node,Node> map = new HashMap<>();
    Node res;
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        generateMap(head);
        generateRandomPtr(head);
        return res;
    }
    private void generateMap(Node head){
        res = new Node(head.val);
        map.put(head,res);
        Node last = res;
        Node cur = head.next;
        while(cur != null){
            Node curRes = new Node(cur.val);
            last.next = curRes;
            last = curRes;
            map.put(cur,last);
            cur = cur.next;
        }
    }
    private void generateRandomPtr(Node head){
        Node cur = res;
        while(head != null){
            if(head.random != null){
                cur.random = map.get(head.random);
            }
            head = head.next;
            cur = cur.next;
        }
    }
}

方法二

class Solution {
    HashMap<Node,Node> map = new HashMap<>();
    Node res;
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        while(cur != null){
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = cur.next.next;
        }
        cur = head;
        while(cur != null){
            if(cur.random != null){
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        Node oldList = head;
        Node newList = head.next;
        res = newList;
        while(oldList != null){
            oldList.next = oldList.next.next;
            oldList = oldList.next;
            if(newList.next != null){
                newList.next = newList.next.next;
                newList = newList.next;
            }
        }
        return res;
    }
}