## Question

>[Leetcode 138. Copy List with Random Pointern](https://leetcode.com/problems/copy-list-with-random-pointer/)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O()
- Space complexity: O()

:::

<br>

## Thoughts & Solutions

### YC
- create a copy of each node and insert the copied node as the next node of the original node
:::spoiler Code

var copyRandomList = function(head) {
    if (!head) {
        return null;
    }

    let curr = head;
    while (curr) {
        const copyNode = new Node(curr.val, curr.next, null);
        curr.next = copyNode;
        curr = copyNode.next;
    }


    curr = head;
    while (curr) {
        if (curr.random) { 
            curr.next.random = curr.random.next;
        }
        curr = curr.next.next;
    }
    
    const copiedHead = head.next;
    let originalCurr = head; // 7
    let copiedCurr = copiedHead; // 7'

    while (originalCurr) { 
        originalCurr.next = originalCurr.next.next; 
        copiedCurr.next = copiedCurr.next ? copiedCurr.next.next : null;
        originalCurr = originalCurr.next;
        copiedCurr = copiedCurr.next;
    }

    return copiedHead;
};

:::

<hr/>

### Sol
==Construct a deep copy of the list.== None of the pointers in the new list should point to nodes in the original list.

1. store the mapping(old Node to new Node)
2. set the pointers


:::spoiler Code

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {
    // Time Complexity: O(n)
    // Space Complexity: O(n)
    if (!head) return null;
    
    const oldToNewMap = new Map();
    let cur = head;

    while (cur) {
        oldToNewMap.set(cur, new Node(cur.val));
        cur = cur.next;
    }
    
    cur = head;
    while (cur) {
        oldToNewMap.get(cur).next = oldToNewMap.get(cur.next) || null;
        oldToNewMap.get(cur).random = oldToNewMap.get(cur.random) || null;
        cur = cur.next;
    }
    
    return oldToNewMap.get(head);
}

:::

<hr/>

### 東

**Solution 1 - Use hashmap to as a ref between original linked list and built a new one**

Two pass
1) Create all new nodes without any pointer. Store in hash map using original node as key and cloned node as value.
2) By referencing hashmap, connect cloned nodes with pointer

`Time Complexity O(n) | Space Complexity - O(n)`

:::spoiler Code

var copyRandomList = function(head) {
    if (head === null) {
        return null;
    }

    const cloneRefMap = new Map();
    cloneRefMap.set(null, null);

    let currNode = head;
    while (currNode !== null) {
        const cloneNode = new Node(currNode.val, null, null);
        cloneRefMap.set(currNode, cloneNode);
        currNode = currNode.next;
    }

    currNode = head;
    while (currNode !== null) {
        const currCloneNode = cloneRefMap.get(currNode);
        currCloneNode.next = cloneRefMap.get(currNode.next);
        currCloneNode.random = cloneRefMap.get(currNode.random);
        currNode = currNode.next;
    }

    return cloneRefMap.get(head);
};

:::

**Solution 2 - First built clone nodes as if they are connection nodes of each original node, then seperate into two linked list**

:::spoiler Code

var copyRandomList = function(head) {
    if(!head) {
        return null;
    }

    let curr = head;
    while(curr) {
        const cloneNode = new Node(curr.val, null, null);
        cloneNode.next = curr.next;
        curr.next = cloneNode;
        curr = curr.next.next;
    }

    curr = head;
    while(curr) {
        curr.next.random = curr.random?.next || null;
        curr = curr.next.next;
    }

    const cloneHead = head.next;
    curr = head;
    let cloneCurr = cloneHead;
    while(curr) {
        curr.next = curr.next.next;
        cloneCurr.next = cloneCurr.next?.next || null;
        curr = curr.next;
        cloneCurr = cloneCurr.next;
    }
    return cloneHead;
}

:::

<hr/>

### Jessie

:::spoiler Code

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function (head) {
    let newHead = newHead2 = head;
    const cloneHead = new Map();

    //  一個一個拿head : val出來存進Map
    while (newHead !== null) {
        cloneHead.set(newHead, new Node(newHead.val));
        newHead = newHead.next;
    }

    //  一個一個存next & random進去對應到剛剛存的Map, Key是剛依序存進的head
    while (newHead2 !== null) {

        if (newHead2.next !== null) {
            cloneHead.get(newHead2).next = cloneHead.get(newHead2.next);
        }

        if (newHead2.random !== null) {
            cloneHead.get(newHead2).random = cloneHead.get(newHead2.random);
        }
        
        newHead2 = newHead2.next;
    }

    //  取出Map的頭 = head
    return cloneHead.get(head);
};

:::

<hr/>

### 皮皮

:::spoiler Code

:::

<hr/>

### Howard

:::spoiler Code

def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
    # time complexity: O(n)
    # space complexity: O(n)
    if not head:
        return head
    memo = {}
    current = head

    while current:
        new_current = Node(current.val)
        memo[current] = new_current
        current = current.next

    current = head

    while current:
        memo[current].next = memo.get(current.next)
        memo[current].random = memo.get(current.random)
        current = current.next

    return memo[head]

:::

<hr/>

## Live Coding

:::spoiler (name)

// write your code here

:::