# 138. Copy List with Random Pointer

### Leetcode

<https://leetcode.com/problems/copy-list-with-random-pointer/>

### 題目

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**](https://en.wikipedia.org/wiki/Object_copying#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.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2019/12/18/e1.png)

```
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:**

![](https://assets.leetcode.com/uploads/2019/12/18/e2.png)

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

**Example 3:**

![](https://assets.leetcode.com/uploads/2019/12/18/e3.png)

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

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

創建一個額外的 newNode 複製原本 oldNode 裡的所有資料

```
/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */
 var copyRandomList = function(head) {
    if(!head) return null;
    
    // 紀錄 oldNode -> newNode 的對照關係
    const hashmap = new Map();
    const getCloneNode = (node) => {
        if(!node) return null;
        if(hashmap.has(node)) return hashmap.get(node);
        else {
            // 初始化新的 node
            hashmap.set(node, new Node(node.val, null, null))
            return hashmap.get(node);
        }
    }
    
    let oldNode = head;
    let newNode = new Node(oldNode.val);
    hashmap.set(oldNode, newNode);
    
    while(oldNode !== null) {
        newNode.next = getCloneNode(oldNode.next);
        newNode.random = getCloneNode(oldNode.random)
        
        oldNode = oldNode.next;
        newNode = newNode.next;
    }
    
    return hashmap.get(head);
};
```

Runtime: 76 ms, faster than 70.86% of JavaScript online submissions for Copy List with Random Pointer.

Memory Usage: 40.7 MB, less than 11.89% of JavaScript online submissions for Copy List with Random Pointer.

Time Complexity : O(N)

Space Complexity : O(N) -> hashmap

* **方法二**

創建一個 linked list，使得原本的 A -> B -> C 變成 A -> A' -> B -> B' -> C -> C'，再取得 A' -> B' -> C' 極為答案

For example:

A -> B -> C

1. 先 copy 所有 node 的 val，並使其指向變成 A -> A' -> B -> B' -> C -> C'
2. 校正 A' B' C' 的 random 指向
3. 恢復讓 head 變成 A -> B -> C，以及回傳新的 linked list A' -> B' -> C'

```
var copyRandomList = function(head) {
    if(!head) return null;
    
    let pointer = head;
    // 1. 
    // make original list A -> B -> C
    // to A -> A' -> B -> B' -> C -> C'
    while(pointer) {
        let newNode = new Node(pointer.val, null, null);
        newNode.next = pointer.next;
        pointer.next = newNode;
        pointer = newNode.next;
    }
    
    pointer = head;
    // 2.
    // make cloned node point to correct random
    while(pointer) {
        pointer.next.random = pointer.random !== null ? pointer.random.next : null;
        pointer = pointer.next.next;
    }
    
    // 3.
    // 此時 head 為 A -> A' -> B -> B' -> C -> C'
    // 要將 head 變回原本的 A -> B -> C
    // 並且回傳 A' -> B' -> C'
    let ptr_old_list = head; // A -> B -> C
    let ptr_new_list = head.next; // A' -> B' -> C'
    const head_old = head.next;
    while(ptr_old_list) {
        // 將 head 變回原本的 A -> B -> C
        ptr_old_list.next = ptr_old_list.next.next;
        ptr_old_list = ptr_old_list.next;
        
        // 產出 A' -> B' -> C'
        ptr_new_list.next = ptr_new_list.next ? ptr_new_list.next.next : null;
        ptr_new_list = ptr_new_list.next;
    }
    
    return head_old;
};
```

Runtime: 87 ms, faster than 21.46% of JavaScript online submissions for Copy List with Random Pointer.

Memory Usage: 40.1 MB, less than 88.71% of JavaScript online submissions for Copy List with Random Pointer.

Time Complexity : O(N)

Space Complexity : O(1)
