Copy List with Random Pointer
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Each node has a next pointer and a random pointer to any node (or none). Make a deep copy of the whole list.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1A copy of node X must point to the COPY of X's random node, not the original. How do you find a copy given the original?
- Hint 2A dictionary: original node -> copy node.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A family tree where each person points to their "next sibling" and to one random relative. To photocopy the family you first make a clone of every person and keep a register: "Original Ravi -> Clone Ravi". Only then do you wire the clones, looking up the register to find which clone a pointer should aim at.
- The obvious way
Without a map you would search the copy list for the right node each time: O(n²).
- The key insight
Pass 1: walk the original list and create a plain copy of every node (just the value), storing original -> copy in a dictionary. Pass 2: walk again and set each copy's next and random by looking up the copies of the original's next and random.
- The algorithm
- Walk the original; for each node create a copy and record original -> copy.
- Walk again. For each original node, find its copy.
- Set copy.next = copy of original.next; copy.random = copy of original.random (none stays none).
- Return the copy of the head.
Watch it run
Examplenodes A -> B -> C; A.random = C, B.random = A, C.random = B
Pass 1: make a clone of each node and write the register.
A -> A', B -> B', C -> C'
Where people slip
- Map None/null to itself so a missing next or random needs no special case.
- An O(1)-space trick exists: weave each copy after its original, wire random, then unweave.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
# Node has .val, .next, .random
def copy_random_list(head):
clone = {None: None} # original -> copy (None maps to None)
node = head
while node: # pass 1: make the copies
clone[node] = Node(node.val)
node = node.next
node = head
while node: # pass 2: wire the pointers
clone[node].next = clone[node.next]
clone[node].random = clone[node.random]
node = node.next
return clone[head]Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.