The algorithm calls dfs on the next pointer of node 1, which is null, to end recursion on next pointers.
💡 Base case reached for next pointer recursion.
Line:copy.next = dfs(node.next)
💡 Null next pointers terminate recursion.
traverse
Recursively copy random pointer of node (val=1)
The algorithm now copies the random pointer of node 1, which points to node 7 (id=0).
💡 Random pointers can point anywhere; recursion handles this similarly to next pointers.
Line:copy.random = dfs(node.random)
💡 Random pointers are copied by recursive calls, possibly revisiting nodes.
prune
Return copy of node (val=7) from memoization
Since node 7 was already copied, the algorithm returns the existing copy from the memoization map to assign as random pointer.
💡 Memoization avoids duplicate copies and infinite recursion.
Line:if node in old_to_new:
return old_to_new[node]
💡 Memoization map is key to efficient copying.
connect
Assign random pointer of copied node (val=1) to copied node (val=7)
The random pointer of the copied node 1 is set to the copied node 7, completing the random pointer assignment for node 1.
💡 Assigning random pointers completes the deep copy structure.
Line:copy.random = dfs(node.random)
💡 Random pointers link copied nodes correctly.
traverse
Recursively copy random pointer of node (val=10)
The algorithm copies the random pointer of node 10, which points to node 11 (id=2).
💡 Random pointers may point forward or backward; recursion handles all cases.
Line:copy.random = dfs(node.random)
💡 Random pointer recursion may revisit nodes already copied.
prune
Return copy of node (val=11) from memoization for random pointer
Node 11 is already copied, so the algorithm returns the existing copy to assign as random pointer of node 10's copy.
💡 Memoization prevents duplicate copies and infinite recursion.
Line:if node in old_to_new:
return old_to_new[node]
💡 Memoization map is reused for random pointers.
connect
Assign random pointer of copied node (val=10) to copied node (val=11)
The random pointer of the copied node 10 is set to the copied node 11, completing this random pointer assignment.
💡 Random pointers link copied nodes correctly to replicate original structure.
Line:copy.random = dfs(node.random)
💡 Random pointers are assigned after next pointers.
reconstruct
Return copied head node
The recursion completes and returns the copied head node representing the deep copied list.
💡 Returning the copied head gives access to the entire copied list.
Line:return dfs(head)
💡 The copied list is fully constructed with correct next and random pointers.
class Node:
def __init__(self, val, next=None, random=None):
self.val = val
self.next = next
self.random = random
def copyRandomList(head):
old_to_new = {}
def dfs(node):
# STEP 2: Check if node is null
if not node:
return None
# STEP 3 & 15: Check memoization
if node in old_to_new:
return old_to_new[node]
# STEP 4,6,8,10,12: Create copy
copy = Node(node.val)
old_to_new[node] = copy
# STEP 5,7,9,11,13: Copy next pointer recursively
copy.next = dfs(node.next)
# STEP 14,17,19: Copy random pointer recursively
copy.random = dfs(node.random)
return copy
# STEP 1 & 20: Start recursion and return copied head
return dfs(head)
if __name__ == '__main__':
nodes = [Node(7), Node(13), Node(11), Node(10), Node(1)]
nodes[0].next = nodes[1]
nodes[1].next = nodes[2]
nodes[2].next = nodes[3]
nodes[3].next = nodes[4]
nodes[1].random = nodes[0]
nodes[2].random = nodes[4]
nodes[3].random = nodes[2]
nodes[4].random = nodes[0]
copied_head = copyRandomList(nodes[0])
print(copied_head.val) # Should print 7
📊
Copy List with Random Pointer - Watch the Algorithm Execute, Step by Step
Watching each recursive call and memoization step reveals how the algorithm avoids infinite loops and ensures a deep copy with correct random pointers.
✓ Memoization is critical to avoid infinite recursion and duplicate copies when copying random pointers.
Without memoization, the algorithm would endlessly recurse on cycles formed by random pointers.
✓ The algorithm copies next pointers first, then random pointers, ensuring the copied list structure is built before linking random pointers.
This order clarifies how the recursion builds the list step-by-step.
✓ Each recursive call corresponds to copying one node, and the visualization shows how the recursion stack grows and shrinks.
Seeing each call separately helps understand recursion depth and flow.
Practice
(1/5)
1. Given the following code snippet implementing the in-place iterative flattening of a multilevel doubly linked list, and the input list: 1 <-> 2 <-> 3, where node 2 has a child list 4 <-> 5, what is the value of curr.val after the first iteration of the outer while loop?
easy
A. 1
B. 4
C. 2
D. 3
Solution
Step 1: Initial state
curr starts at node with val=1. First iteration: curr=1, no child, move to curr.next=2.
Step 2: First iteration with child
curr=2 has child list starting at 4. The code finds tail=5, connects tail.next to curr.next (3), updates pointers, sets curr.next=4, child.prev=2, curr.child=None, then moves curr=curr.next=4.
Final Answer:
Option B -> Option B
Quick Check:
After first iteration, curr moves to child node 4 [OK]
Hint: After splicing child, curr moves to child's head node [OK]
Common Mistakes:
Assuming curr stays at original node after splicing
Forgetting to move curr to next after flattening
Confusing tail with child head
2. You are given a singly linked list and a value x. The task is to reorder the list so that all nodes with values less than x come before nodes with values greater than or equal to x, while preserving the original relative order within each partition. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?
easy
A. Extract all node values into arrays, reorder them, then rebuild the list.
B. Use two pointers to build two separate linked lists for nodes less than and greater or equal to x, then concatenate them.
C. Sort the entire linked list using merge sort and then split at value x.
D. Traverse the list once, rearranging nodes in-place by adjusting pointers without extra lists.
Solution
Step 1: Understand the problem constraints
The problem requires partitioning the list around value x while preserving relative order and achieving O(n) time and O(1) space.
Step 2: Evaluate approaches
Approach A uses extra arrays, so space is O(n). Approach B uses extra lists, so space is O(n). Approach D sorts the list, which is O(n log n) time. Only approach C rearranges nodes in-place in one pass with constant space.
Final Answer:
Option D -> Option D
Quick Check:
In-place rearrangement achieves O(n) time and O(1) space [OK]
Hint: In-place pointer rearrangement is O(1) space [OK]
Common Mistakes:
Assuming sorting is needed to partition
Using extra arrays or lists increases space
Believing two separate lists always use constant space
3. Consider the following buggy recursive code to convert a binary number in a linked list to an integer. Which line contains the subtle bug that causes incorrect output for single-node lists?
medium
A. Line X: using addition instead of bitwise OR to accumulate bits
B. Line 7: base case check for None node
C. Line 3: __init__ method of ListNode
D. Line 9: recursive call with node.next and updated acc
Solution
Step 1: Identify the accumulation operation
The code uses bitwise OR instead of addition to combine bits: acc = (acc << 1) | node.val.
Step 2: Understand impact on single-node lists
Bitwise OR correctly sets bits without carry, ensuring accurate accumulation for all list lengths.
Final Answer:
Option A -> Option A
Quick Check:
Bitwise OR correctly sets bits without carry, addition may overflow [OK]
Hint: Use bitwise OR, not addition, to accumulate bits [OK]
Common Mistakes:
Using + instead of | causes wrong bit accumulation
Misunderstanding bitwise operations vs arithmetic
Assuming addition and OR are interchangeable for bits
4. Identify the bug in the following code snippet for splitting a linked list into k parts:
medium
A. Line where curr is advanced without checking if curr is None, causing AttributeError.
B. Line where tails[i].next is set to curr without checking if curr is None.
C. Line where tails[i].next is set to None, which breaks the list prematurely.
D. Line where dummy_heads are created, which wastes extra space.
Solution
Step 1: Analyze pointer advancement
Inside the inner loop, curr is advanced with curr = curr.next without checking if curr is None.
Step 2: Identify potential error
If curr is None, accessing curr.next raises AttributeError. The check must happen before advancing curr.
Hint: Always check curr is not None before accessing curr.next [OK]
Common Mistakes:
Forgetting None check before pointer advance
Incorrectly cutting list by setting next to None too early
Misusing dummy heads
5. Suppose the problem is modified so that nodes can be reused multiple times (i.e., after reversing a group, nodes can appear again in subsequent groups). Which of the following changes to the algorithm correctly handles this scenario?
hard
A. Modify the algorithm to create new nodes for each group reversal to avoid modifying original nodes in place.
B. This problem cannot be solved by reversal; instead, use a queue to simulate repeated node usage.
C. Use recursion with memoization to store reversed groups and reuse them without modifying the original list.
D. Use the same iterative reversal approach but reset pointers to allow reusing nodes in multiple groups.
Solution
Step 1: Understand node reuse implication
Reusing nodes means original nodes must remain unchanged or duplicated to appear multiple times.
Step 2: Evaluate algorithm modifications
In-place reversal modifies nodes destructively, so creating new nodes for each group is necessary to preserve original nodes.
Step 3: Assess other options
Resetting pointers (A) breaks list integrity; recursion with memoization (C) is complex and not standard; queue simulation (B) does not solve reversal reuse.
Final Answer:
Option A -> Option A
Quick Check:
Duplicating nodes preserves original list for reuse [OK]
Hint: Node reuse requires duplication, not in-place reversal [OK]
Common Mistakes:
Trying to reuse nodes in place
Ignoring list integrity
Assuming recursion memoization solves reuse
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.