Copy List with Random Pointer

How it works

This method also avoids extra space like a hash map, but instead of inserting copied nodes into the next pointer chain, we temporarily use the random pointer to store the copied nodes.

For every original node:

• We create its copy and store it in the original node’s random pointer.
• The copy’s next pointer initially points to whatever the original node’s random was pointing to.

This allows us to:

1. Create all copies without extra memory.
2. Fix the random pointers of the copied nodes using the original structure.
3. Reconnect the next pointers to build the final deep-copy list.
4. Restore the original list.

Everything happens using only pointer manipulations — no extra arrays, no hash map.

Steps

1. Create all copied nodes

   • For each original node A, create a copy A'.
   • Store this copy inside A.random.
   • Set A'.next = A.random_old.

2. Fix random pointers of copies

   • For each original node A, set A'.random = A.random_old.random' (if exists).

3. Extract the copied list and restore original list

   • For each original node A:
     • Restore A.random = original_random.
     • Connect A'.next to the next copied node.

4. Return the head of the copied list (which is head.random).

Complexity

• Time complexity: O(n)
• Space complexity:
  • O(1) extra space.
  • O(n) for the output.

Things to watch for

Creating Multiple Copies of the Same Node

Without a hash map to track already-copied nodes, you might create duplicate copies when multiple random pointers point to the same node. Always check if a node has been copied before creating a new copy.

Forgetting to Handle Null Random Pointers

The random pointer can be null. Attempting to access properties of null causes crashes. Always check for null before dereferencing.

Not Restoring Original List in Space-Optimized Solutions

In the interleaving approach, failing to properly unweave the two lists corrupts the original list and may break the copied list's pointers. The separation step must correctly restore both next pointers.

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if head is None:
            return None

        l1 = head
        while l1:
            l2 = Node(l1.val)
            l2.next = l1.random
            l1.random = l2
            l1 = l1.next

        newHead = head.random

        l1 = head
        while l1:
            l2 = l1.random
            l2.random = l2.next.random if l2.next else None
            l1 = l1.next

        l1 = head
        while l1 is not None:
            l2 = l1.random
            l1.random = l2.next
            l2.next = l1.next.random if l1.next else None
            l1 = l1.next

        return newHead

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

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) {
            return nullptr;
        }

        Node* l1 = head;
        while (l1) {
            Node* l2 = new Node(l1->val);
            l2->next = l1->random;
            l1->random = l2;
            l1 = l1->next;
        }

        Node* newHead = head->random;

        l1 = head;
        while (l1) {
            Node* l2 = l1->random;
            l2->random = (l2->next != nullptr) ? l2->next->random : nullptr;
            l1 = l1->next;
        }

        l1 = head;
        while (l1) {
            Node* l2 = l1->random;
            l1->random = l2->next;
            l2->next = (l1->next != nullptr) ? l1->next->random : nullptr;
            l1 = l1->next;
        }

        return newHead;
    }
};