105.Copy List with Random Pointer

1.Description(Medium)

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val

• random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Constraints:

• 0 <= n <= 1000

• -104 <= Node.val <= 104

• Node.random is null or is pointing to some node in the linked list.

2.Code

跟copy graph相似

https://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73016

Solution 1:用HashMap表示新老节点映射（耗费O(n)的空间）

两次for构建先next连起来，再Random pointer连起来

Solution 2: 用O(1)空间做。用next存mapping信息

Version 1：HashMap

首先得弄懂深拷贝的含义，深拷贝可不是我们平时见到的对基本类型的变量赋值那么简单，深拷贝常常用于对象的克隆。这道题要求深度拷贝一个带有 random 指针的链表，random 可能指向空，也可能指向链表中的任意一个节点。

对于通常的单向链表，我们依次遍历并根据原链表的值生成新节点即可，原链表的所有内容便被复制了一份。但由于此题中的链表不只是有 next 指针，还有一个随机指针，故除了复制通常的 next 指针外还需维护新链表中的随机指针。容易混淆的地方在于原链表中的随机指针指向的是原链表中的节点，深拷贝则要求将随机指针指向新链表中的节点。

所有类似的深度拷贝题目的传统做法，都是维护一个hash table。即先按照复制一个正常链表的方式复制，复制的时候把复制的结点做一个hash table，以旧结点为 key，新节点为 value。这么做的目的是为了第二遍扫描的时候我们按照这个哈希表把结点的 random 指针接上。

深拷贝步骤如下；

1. 根据 next 指针新建链表

2. 维护新旧节点的映射关系

3. 拷贝旧链表中的 random 指针

4. 更新新链表中的 random 指针

其中1, 2, 3 可以合并在一起。

1. 只需要一个dummy存储新的拷贝出来的链表头，以用来第二次遍历时链接 random 指针。所以第一句异常检测可有可无。

2. 第一次链接时勿忘记同时拷贝 random 指针，但此时的 random 指针并没有真正“链接”上，实际上是链接到了原始链表的 node 上。

3. 第二次遍历是为了把原始链表的被链接的 node 映射到新链表中的 node，从而完成真正“链接”。

class RandomListNode {
    int label;
    RandomListNode next, random;
    RandomListNode(int x) { this.label = x; }
};

public class Solution_105 {

     /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */


    public RandomListNode copyRandomList(RandomListNode head) {
        if(head==null){
            return null;
        }

        HashMap<RandomListNode,RandomListNode> map=new HashMap<>();
        RandomListNode dummy=new RandomListNode(0);
        RandomListNode current=dummy;//dummy 是用来链接新的链表
        //first loop for stage 1 2 3
        while(head!=null){
            //create a new node
            RandomListNode newnode=new RandomListNode(head.label);
            //link new node next pointer
            current.next=newnode;
            //map new node to old node
            map.put(head, newnode);
            //copy old node random pointer
            newnode.random=head.random;
            head=head.next;
            current=current.next;
        }

        //second loop for stage 4
        current=dummy.next;
        while(current!=null){
            if(current.random!=null){
                RandomListNode copyrandom=map.get(current.random);
                current.random=copyrandom;
            }
            current=current.next;
        }
        return dummy.next;
    }

}