Copy List with Random Pointer

▶

Steps

setup

Start copying from head node (val=7)

The algorithm begins by calling dfs on the head node with value 7 to start the deep copy process.

💡 Starting at the head is essential because the entire list is reachable from here.

Line:

return dfs(head)

💡 The recursion will traverse all nodes reachable from head.

compare

Check if current node (val=7) is null

The algorithm checks if the current node is null to handle the base case of recursion.

💡 This base case prevents infinite recursion and signals when to stop.

Line:

if not node:
    return None

💡 Non-null nodes must be copied; null nodes return None.

compare

Check if node (val=7) already copied

The algorithm checks if the current node has already been copied by looking it up in the memoization map.

💡 Memoization prevents duplicate copies and infinite loops with random pointers.

Line:

if node in old_to_new:
    return old_to_new[node]

💡 Memoization map tracks nodes already copied.

insert

Create copy of node (val=7)

A new node with value 7 is created as a copy of the current node and stored in the memoization map.

💡 Creating a copy node is the core of the deep copy process.

Line:

copy = Node(node.val)
old_to_new[node] = copy

💡 Each original node maps to exactly one copied node.

traverse

Recursively copy next pointer of node (val=7)

The algorithm calls dfs on the next node (val=13) to copy the next pointer of the copied node.

💡 Recursively copying next pointers builds the copied list structure.

Line:

copy.next = dfs(node.next)

💡 Next pointers are copied by recursive calls.

insert

Create copy of node (val=13)

A new node with value 13 is created as a copy of the current node and stored in the memoization map.

💡 Each node encountered is copied once and memoized.

Line:

copy = Node(node.val)
old_to_new[node] = copy

💡 Memoization map grows as new nodes are copied.

traverse

Recursively copy next pointer of node (val=13)

The algorithm calls dfs on the next node (val=11) to copy the next pointer of the copied node 13.

💡 Recursion continues down the next pointers to copy the entire list.

Line:

copy.next = dfs(node.next)

💡 Next pointers form a chain of recursive calls.

insert

Create copy of node (val=11)

A new node with value 11 is created and stored in the memoization map.

💡 Each node is copied exactly once to maintain structure.

Line:

copy = Node(node.val)
old_to_new[node] = copy

💡 Memoization map ensures unique copies.

traverse

Recursively copy next pointer of node (val=11)

The algorithm calls dfs on the next node (val=10) to copy the next pointer of the copied node 11.

💡 Recursion continues to copy the entire next chain.

Line:

copy.next = dfs(node.next)

💡 Next pointers are copied in order.

insert

Create copy of node (val=10)

A new node with value 10 is created and stored in the memoization map.

💡 Copying continues for each node in the list.

Line:

copy = Node(node.val)
old_to_new[node] = copy

💡 Each node is uniquely copied and memoized.

traverse

Recursively copy next pointer of node (val=10)

The algorithm calls dfs on the next node (val=1) to copy the next pointer of the copied node 10.

💡 Recursion continues until the end of the list.

Line:

copy.next = dfs(node.next)

💡 Next pointers form a chain of recursive calls until null.

insert

Create copy of node (val=1)

A new node with value 1 is created and stored in the memoization map.

💡 The last node is copied to complete the list.

Line:

copy = Node(node.val)
old_to_new[node] = copy

💡 Memoization map now contains all nodes.

traverse

Recursively copy next pointer of node (val=1)

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.

advance

7

→

13

→

11

→

10

→

1

compare

7

→

13

→

11

→

10

→

1

compare

7

→

13

→

11

→

10

→

1

insert

7

→

13

→

11

→

10

→

1

→

7

advance

7

→

13

→

11

→

10

→

1

→

7

insert

7

→

13

→

11

→

10

→

1

→

7

→

13

advance

7

→

13

→

11

→

10

→

1

→

7

→

13

insert

7

→

13

→

11

→

10

→

1

→

7

→

13

→

11

advance

7

→

13

→

11

→

10

→

1

→

7

→

13

→

11

insert

7

→

13

→

11

→

10

→

1

→

7

→

13

→

11

→

10

advance

7

→

13

→

11

→

10

→

1

→

7

→

13

→

11

→

10

insert

7

→

13

→

11

→

10

→

1

→

7

→

13

→

11

→

10

→

1

compare

7

→

13

→

11

→

10

→

1

→

7

→

13

→

11

→

10

→

1

advance

7

→

13

→

11

→

10

→

1

→

7

→

13

→

11

→

10

→

1

prune

7

→

13

→

11

→

10

→

1

→

7

→

13

→

11

→

10

→

1

connect

7

→

13

→

11

→

10

→

1

advance

10

→

11

→

7

→

13

→

11

→

10

→

1

prune

11

→

10

connect

7

→

13

→

11

→

10

→

1

reconstruct

7

→

13

→

11

→

10

→

1

Result: [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]

Key Takeaways

✓ 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. Given the following code for partitioning a linked list around value x = 3, and the input list: 1 -> 4 -> 2 -> 5, what is the final reordered list returned by the function?

easy

A. 1 -> 4 -> 2 -> 5

B. 1 -> 2 -> 4 -> 5

C. 2 -> 1 -> 4 -> 5

D. 4 -> 1 -> 2 -> 5

Solution

1. Step 1: Trace initial pointers with input 1 -> 4 -> 2 -> 5 and x=3

   Start with dummy -> 1 -> 4 -> 2 -> 5, less_tail and prev at dummy, current at 1.

2. Step 2: Process nodes

   Node 1 < 3, less_tail.next == current, move less_tail and prev forward. Node 4 >= 3, move prev and current forward. Node 2 < 3, less_tail.next != current, so remove 2 and insert after less_tail. Final list: 1 -> 2 -> 4 -> 5.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Nodes less than 3 appear first in original order, then others [OK]

Hint: Track less_tail and prev carefully to avoid skipping nodes [OK]

Common Mistakes:

• Swapping values instead of nodes
• Incorrect pointer updates causing lost nodes
• Assuming order changes within partitions

2. Given the following code snippet for splitting a linked list into k=3 parts, and the input list 1->2->3->4, what is the returned list of parts (values only)?

easy

A. [[1, 2], [3, 4], []]

B. [[1, 2], [3], [4]]

C. [[1, 2], [3], [4, None]]

D. [[1], [2], [3, 4]]

Solution

1. Step 1: Calculate total nodes and part sizes

   Total nodes = 4, k = 3, so part_size = 1, remainder = 1. First remainder parts get one extra node.

2. Step 2: Assign nodes to parts

   Part 0 size = 2 nodes (1,2), Part 1 size = 1 node (3), Part 2 size = 1 node (4). The returned parts are [[1,2],[3],[4]].

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum of parts equals original list length and sizes differ by at most one [OK]

Hint: Remainder nodes assigned to first parts -> first part larger [OK]

Common Mistakes:

• Assigning remainder nodes to last parts
• Off-by-one in part sizes
• Returning fewer than k parts

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

1. Step 1: Identify the accumulation operation

   The code uses bitwise OR instead of addition to combine bits: acc = (acc << 1) | node.val.

2. Step 2: Understand impact on single-node lists

   Bitwise OR correctly sets bits without carry, ensuring accurate accumulation for all list lengths.

3. Final Answer:

   Option A -> Option A

4. 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. What is the time complexity of the in-place iterative flattening algorithm for a multilevel doubly linked list with total n nodes, considering the worst-case scenario where each node has a child list?

medium

A. O(n) amortized, since the total number of pointer updates and traversals sums to linear over all nodes.

B. O(n) because each node is visited a constant number of times during the flattening process.

C. O(n^2) because for each node with a child, we traverse its entire child list to find the tail.

D. O(n log n) due to repeated tail searches in nested child lists.

Solution

1. Step 1: Analyze tail-finding loop

   Although tail is found by traversing child lists, each node is visited at most once as tail or curr.

2. Step 2: Amortized analysis

   All next pointers are traversed linearly; tail searches do not overlap nodes multiple times, so total work is linear.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each node processed once, tail searches amortize to O(n) [OK]

Hint: Tail searches look nested but total visits are linear [OK]

Common Mistakes:

• Assuming tail search is repeated fully for each child causing O(n^2)
• Confusing amortized with worst-case per iteration
• Ignoring that nodes are not revisited multiple times

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

1. Step 1: Understand node reuse implication

   Reusing nodes means original nodes must remain unchanged or duplicated to appear multiple times.

2. Step 2: Evaluate algorithm modifications

   In-place reversal modifies nodes destructively, so creating new nodes for each group is necessary to preserve original nodes.

3. 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.

4. Final Answer:

   Option A -> Option A

5. 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