# 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.

# Solution

Approach 1: Hash map.

Approach 2: No extra space by linking the copied node to the original one temporarily.

# Code (Python)

Approach 1:

    def copyRandomList(self, head: 'Node') -> 'Node':
        # idea: use a hash table for {original_node: copied_node} for each node in the list. Time: O(N), space: O(N).
        # Alternatively there's a time: O(N), space: O(1) solution -- build a copied node right after each original node, assign random pointers, then extract those copied nodes
        if not head:
            return None
        
        node_map = {}
        node = head
        while node:
            node_map[node] = Node(node.val)
            node = node.next
        for original_node, new_node in node_map.items():
            if original_node.next:
                new_node.next = node_map[original_node.next]
            if original_node.random:
                new_node.random = node_map[original_node.random]
        return node_map[head]

# Code (C++)

Approach 1:

/*
// 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;
    }
};
*/
// Hash map.
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == NULL)
            return NULL;
        unordered_map<Node*,Node*> created;
        Node *curr = head;
        while (curr)
        {
            Node *newCurr = new Node(curr->val, NULL, NULL);
            created[curr] = newCurr;
            curr = curr->next;
        }
        curr = head;
        while (curr)
        {
            created[curr]->next = created[curr->next];
            created[curr]->random = created[curr->random];
            curr = curr->next;
        }
        return created[head];
    }
};

Approach 2:

// No extra space by linking the copied node to the original one temporarily.
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == NULL)
            return NULL;
        Node *curr = head;
        while (curr)
        {
            Node *newCurr = new Node(curr->val, NULL, NULL);
            newCurr->next = curr->next;
            curr->next = newCurr;
            curr = newCurr->next;
        }
        curr = head;
        while (curr)
        {
            Node *newCurr = curr->next;
            if (curr->random)
                newCurr->random = curr->random->next;
            curr = curr->next->next;
        }
        Node *newHead = head->next;
        curr = head;
        while (curr)
        {
            Node *newCurr = curr->next;
            curr->next = newCurr->next;
            if (curr->next)
                newCurr->next = curr->next->next;
            curr = curr->next;
        }
        return newHead;
    }
};