LeetCode/138. 复制带随机指针的链表

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

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

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

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

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

提示：

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

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题解法五花八门，我在这里提供一种思路最简单的方法，就是利用HashMap。我们首先遍历一次链表，将每个结点复制一个相同的新结点并存入HashMap中，其中Key为原结点，Value为原结点的复制结点，第一遍遍历不用管每个结点的next和random指针。第二遍遍历链表，我们要利用每个原结点的next和random指针信息来完善新的复制链表，其中，新结点的next指向的就是原始结点next指向的结点对应的复制结点，即map.get(p).next = map.get(p.next);，新结点的random指向的就是原始结点的random所对应的复制结点，即map.get(p).random = map.get(p.random);最后我们返回HashMap中head对应的Value，即新的复制链表的头结点。

具体代码如下：

/*
// 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 head;

        Node p = head;
      	//创建HashMap用来存放原始链表和新链表的对应关系
        Map<Node, Node> map = new HashMap<>();
        while (p != null) {
            Node temp = new Node(p.val);
          	//将每个原始结点拷贝一份，其中原始结点作为Key，复制结点作为Value
            map.put(p, temp);
            p = p.next;
        }

        p = head;
        while (p != null) {
          	//新结点的next就是原结点next指向的结点的复制结点
            map.get(p).next = map.get(p.next);
          	//新结点的random结点就是原始结点random指向的结点的复制结点
            map.get(p).random = map.get(p.random);
            p = p.next;
        }
				//返回新链表的头结点即可
        return map.get(head);
    }
}