The O(n) Club: Copy List with Random Pointer – How to Not Clone a Dumpster Fire

The O(n) Club: Copy List with Random Pointer – How to Not Clone a Dumpster Fire

⚡ TL;DR

Linked list problem but with a spicy random pointer: copy both next and random, with zero references to the original. Hash map is easy; interleaving is magic. Java hash map brute force below:

// HashMap: Java edition
Map<Node, Node> map = new HashMap<>();
Node curr = head;
while (curr != null) {
    map.put(curr, new Node(curr.val));
    curr = curr.next;
}
curr = head;
while (curr != null) {
    map.get(curr).next = map.get(curr.next);
    map.get(curr).random = map.get(curr.random);
    curr = curr.next;
}
return map.get(head);

🧠 How Devs Usually Mess This Up

Oh look, you cloned only the values but left all the pointers wired to the old list. Result? Your “deep copy” is a dangerous lookalike still stalking the original. Or you copied random by reference, so the copy and original are now awkwardly co-dependent. And if you only reach for a HashMap, you’re missing the in-place O(1) solution—pointer gymnastics, but far less RAM guilt.

🔍 What’s Actually Going On

Picture a party: everyone (node) sits in order (next), but everyone also points at a random guest (random). Deep copying means duplicating the party—AND the random drama—without a single original crashers left in the new universe. Enter the interleaving trick: insert copies after originals (conga-line style), wire up the clones’ randoms using this new order, then peel the worlds apart. It’s quantum entanglement for Java objects.

🛠️ PseudoCode

• Interleave: For each node, stick its twin after it.
  

  Node curr = head;
  while (curr != null) {
      Node copy = new Node(curr.val);
      copy.next = curr.next;
      curr.next = copy;
      curr = copy.next;
  }

  Why? Each copy is predictably right after its source—setup for random magic.
• Set randoms: Make each copy’s random pointer match the original’s—pointing ONLY at a copy.
  

  curr = head;
  while (curr != null) {
      if (curr.random != null) {
          curr.next.random = curr.random.next;
      }
      curr = curr.next.next;
  }

  Why? Clones piggyback originals, so copies of randoms are at curr.random.next.
• Unweave: Carefully untangle the original list and your new deep copy.
  

  curr = head;
  Node pseudoHead = new Node(0);
  Node copyCurr = pseudoHead;
  while (curr != null) {
      Node nextOrig = curr.next.next;
      Node copy = curr.next;
      copyCurr.next = copy;
      copyCurr = copy;
      curr.next = nextOrig;
      curr = nextOrig;
  }
  return pseudoHead.next;
  

  Why? Snap apart the conga lines—no more entanglement. Originals and dopplegängers, finally separate.

💻 The Code

// Fancy O(1) space solution:
class Node {
    int val;
    Node next;
    Node random;
    Node(int v) { val = v; }
}
public Node copyRandomList(Node head) {
    if (head == null) return null;
    Node curr = head;
    // Step 1: Interleave
    while (curr != null) {
        Node copy = new Node(curr.val);
        copy.next = curr.next;
        curr.next = copy;
        curr = copy.next;
    }
    // Step 2: Connect random pointers
    curr = head;
    while (curr != null) {
        if (curr.random != null) {
            curr.next.random = curr.random.next;
        }
        curr = curr.next.next;
    }
    // Step 3: Separate
    curr = head;
    Node pseudoHead = new Node(0);
    Node copyCurr = pseudoHead;
    while (curr != null) {
        Node copy = curr.next;
        copyCurr.next = copy;
        copyCurr = copy;
        curr.next = copy.next;
        curr = curr.next;
    }
    return pseudoHead.next;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Random can be null and so can your dignity—always check before you assign.
• If you miswire even one pointer, you’re in bug city (or infinite loop purgatory).
• HashMap uses O(n) space—safe, but your interviewer will judge in silence.
• Mess up interleaving, and untangling the lists will be its own random mess.

🧠 Interviewer Brain-Tattoo

“If your deep copy still stalks the original, congratulations: you built a bug that’s impossible to debug. Don’t cross the streams.”