Copy a List With Random Links
Linked Lists: lesson 9 of 10
Clone the nodes first, wire the pointers second.
Lesson 9 of 10 · 6 min
Copy a List With Random Links
Step 1 of 9
Each node points at the next one and at any node at all. b's random link aims backwards; a's aims forwards.
The Idea
Each node carries a second pointer that can aim anywhere — forwards, backwards, at itself. Copying in one pass is impossible: the target may not exist yet.
So split it. Pass one creates a bare copy of every node and records old to new. Pass two reads that map and translates both links. O(n) time, O(n) space.
Real-World Example
Redrawing a seating chart where each guest also names a person they must be able to see. You write every name onto the new chart first, then draw the sight-lines — because you cannot point at a chair you have not drawn.
The Code
class Node:
def __init__(self, v): self.val, self.next, self.rand = v, None, None
def copy(head):
clone = {None: None} # old node -> its fresh copy
n = head
while n: clone[n] = Node(n.val); n = n.next # pass 1: bare copies
n = head
while n: # pass 2: translate both fields
clone[n].next, clone[n].rand = clone[n.next], clone[n.rand]
n = n.next
return clone[head]
a, b = Node("a"), Node("b")
a.next, a.rand, b.rand = b, b, b
c = copy(a)
print(c.val, c.next.val, c.rand is b, c.rand is c.next) # a b False TrueYour turn
Fill in the blank.
class Node:
def __init__(self, v): self.val, self.next, self.rand = v, None, None
a, b = Node("a"), Node("b")
a.next, a.rand, b.rand = b, b, b
clone = {None: None}
n = a
while n: clone[n] = Node(n.val); n = n.next
n = a
while n:
clone[n].next, clone[n].rand = clone[n.next], ___
n = n.next
print(clone[a].rand is clone[b]) # should print TrueMini quiz
1 / 3