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

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

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

3. Final Answer:

   Option D -> Option D

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

2. Consider the following Python code implementing the recursive reorder list approach. Given the input list 1->2->3, what is the printed output after calling reorderList(n1)?

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorderList(head):
    def helper(front, back):
        if not back:
            return True
        if not helper(front, back.next):
            return False
        if front[0] == back or front[0].next == back:
            back.next = None
            return False
        tmp = front[0].next
        front[0].next = back
        back.next = tmp
        front[0] = tmp
        return True
    helper([head], head)

n3 = ListNode(3)
n2 = ListNode(2, n3)
n1 = ListNode(1, n2)
reorderList(n1)
curr = n1
while curr:
    print(curr.val, end=' ')
    curr = curr.next

easy

A. 1 3

B. 1 2 3

C. 1 3 2

D. 3 2 1

Solution

1. Step 1: Trace helper calls with input 1->2->3

   Recursion reaches back=null, then unwinds, linking nodes alternately: 1->3->2.

2. Step 2: Verify final list traversal output

   Prints nodes in order: 1 3 2, confirming correct reorder.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches reorder pattern for 3 nodes [OK]

Hint: Small input trace confirms reorder sequence [OK]

Common Mistakes:

• Assuming no reorder happens
• Stopping recursion too early
• Misplacing next pointers

3. Given the following code snippet for reversing nodes in k-groups, and the input list 1->2->3->4 with k=2, what is the value of group_prev.next.val after the first group reversal?

easy

A. 4

B. 1

C. 3

D. 2

Solution

1. Step 1: Trace first group reversal

   Input list: 1->2->3->4, k=2. First group is nodes 1 and 2. After reversal, group becomes 2->1.

2. Step 2: Identify group_prev.next after reversal

   Initially, group_prev is dummy pointing to 1. After reversal, group_prev.next points to 2, the new head of reversed group.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   First group's head after reversal is node with value 2 [OK]

Hint: First group's head after reversal is the kth node [OK]

Common Mistakes:

• Confusing original head with new head after reversal
• Off-by-one in counting nodes
• Misunderstanding pointer updates

4. What is the time and space complexity of the optimal in-place partition algorithm for a linked list of length n around value x?

medium

A. Time: O(n), Space: O(1)

B. Time: O(n), Space: O(n)

C. Time: O(n^2), Space: O(1)

D. Time: O(n log n), Space: O(1)

Solution

1. Step 1: Identify complexity of outer and inner loops

   The algorithm traverses the list once, performing constant-time pointer operations per node, so time is O(n).

2. Step 2: Check if recursion stack adds extra space

   No recursion or extra data structures are used; only a few pointers are maintained, so space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with constant pointers -> O(n) time and O(1) space [OK]

Hint: Single pass with pointer updates -> O(n) time, O(1) space [OK]

Common Mistakes:

• Confusing with sorting complexity O(n log n)
• Assuming extra arrays cause O(n) space
• Mistaking pointer updates as nested loops causing O(n^2)

5. Suppose the linked list nodes can be reused multiple times (i.e., the list is circular or nodes can appear multiple times). Which modification to the odd-even rearrangement algorithm is necessary to handle this scenario correctly?

hard

A. Add a visited set to track nodes already processed to avoid infinite loops or duplicates

B. No modification needed; the original in-place algorithm works correctly even with reused nodes

C. Convert the list to an array first, then reorder and reconstruct the list to handle duplicates

D. Use recursion to process nodes and detect cycles automatically

Solution

1. Step 1: Identify problem with reused nodes

   If nodes are reused or list is circular, naive pointer traversal causes infinite loops or duplicates.

2. Step 2: Use a visited set

   Tracking visited nodes prevents revisiting and infinite loops, ensuring correct rearrangement.

3. Step 3: Why other options fail

   No modification ignores cycles; array conversion adds overhead; recursion risks stack overflow without cycle detection.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Visited set is standard for cycle detection in linked lists [OK]

Hint: Detect cycles with visited set to avoid infinite loops [OK]

Common Mistakes:

• Assuming original algorithm handles cycles or reused nodes
• Using recursion without cycle detection