138. Copy List with Random Pointer

1. Description

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.
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) where random pointer points to, or null if it does not point to any node.

2. Example

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]]

Example 4:
Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

3. Constraints

• -10000 <= Node.val <= 10000
• Node.random is null or pointing to a node in the linked list.
• The number of nodes will not exceed 1000.

4. Solutions

Three Iterations

n is the number of nodes in head
Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    Node *copyRandomList(Node *head) {
        for (Node *iter = head; iter != nullptr; iter = iter->next->next) {
            Node *node = new Node(iter->val);
            node->next = iter->next;
            iter->next = node;
        }

        for (Node *iter = head; iter != nullptr; iter = iter->next->next) {
            iter->next->random = iter->random == nullptr ? nullptr : iter->random->next;
        }

        Node *guard = new Node(0);
        guard->next = head;
        for (Node *iter1 = guard, *iter2 = head; iter1 != nullptr && iter2 != nullptr;) {
            iter1->next = iter2->next;
            iter1 = iter1->next;

            iter2->next = iter1->next;
            iter2 = iter2->next;
        }

        return guard->next;
    }
};