138. Copy List with Random Pointer

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

Return a deep copy of the list.

Example 1:

Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Note:

1. You must return the copy of the given head as a reference to the cloned list.

// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};

// Iteration + Hash table
Node* copyRandomList(Node* head) { // time: O(n); space: O(n)
    if (!head) return nullptr;
    unordered_map<Node*, Node*> m;
    Node* cur = head;
    // Copy each node
    while (cur) {
        m[cur] = new Node(cur->val, nullptr, nullptr);
        cur = cur->next;
    }
    // Assign next and random node pointers
    cur = head;
    while (cur) {
        m[cur]->next = m[cur->next];
        m[cur]->random = m[cur->random];
        cur = cur->next;
    }
    return m[head];
}

// Recursion + Hash table
unordered_map<Node*, Node*> m;
Node* copyRandomList(Node* head) { // time: O(n); space: O(n)
    if (!head) return nullptr;
    if (m[head]) return m[head];
    Node* node = new Node(head->val, nullptr, nullptr);
    m[head] = node;
    node->next = copyRandomList(head->next);
    node->random = copyRandomList(head->random);
    return node;
}

// Constant space
Node* copyRandomList(Node* head) { // time: O(n); space: O(1)
    if (!head) return nullptr;
    Node *cur = head, *next = nullptr;
    // Copy each node and append each node to its original node
    while (cur) {
        next = cur->next;
        Node* node = new Node(cur->val, nullptr, nullptr);
        cur->next = node;
        node->next = next;
        cur = next;
    }
    // Assign random Node pointers
    cur = head;
    while (cur) {
        if (cur->random) {
            cur->next->random = cur->random->next;
        }
        cur = cur->next->next;
    }
    // Separate original and duplicate lists
    cur = head;
    
    // Node* res = cur->next;
    // while (cur) {
    //     Node* next = cur->next;
    //     cur->next = next->next;
    //     if (next->next) next->next = next->next->next;
    //     cur = cur->next;
    // }
    // return res;
    
    Node *dummy = new Node(-1e7, nullptr, nullptr), *pre = dummy;
    while (cur) {
        next = cur->next;
        pre->next = next;
        pre = pre->next;
        cur->next = next->next;
        cur = cur->next;
    }
    Node* res = dummy->next;
    delete dummy;
    return res;
}