Clone World: Random Pointer Adventure

📋 OBJECTIVE

Clone a linked list where each node has a random pointer. Do it in O(n) time without a hashmap!

📝 3-STEP ALGORITHM

// Step 1: Interleave
for each original node:
  create clone
  insert clone after original
  
// Step 2: Set random ptrs
for each original node:
  clone.random = 
    original.random.next
    
// Step 3: Unweave
separate original & clone lists

💡 KEY INSIGHT

By interleaving, clone nodes are always at original.next! So original.random.next is exactly the clone of the random target!

🧬 CLONING LAB Ready to clone!

INTERLEAVE
Original + Clone

SET RANDOM
Clone.random = Orig.random.next

UNWEAVE
Separate Lists

🔬 Current Phase

Click "Step" to begin the cloning process!
Watch how we clone without using extra space.

ORIGINAL:

CLONE:

Not created yet...

🔗 INTERLEAVED LIST

🧬 CLONE WORLD

🔬 Current Phase

Success!