#39 Medium Time O(n) Space O(n) Animated

Copy List with Random Pointer

Deep copy a linked list with random pointers.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Pointer rewiring with saved next state

Before changing a link, save the only pointer that would otherwise be lost.

Approach: Hash Map (Two Passes)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Before changing a link, save the only pointer that would otherwise be lost.

Common Pitfall

Always store next before redirecting current.next.

Description

Deep copy a linked list with random pointers.

Constraints

Time Complexity: O(n)
Space Complexity: O(n)

Solution — Hash Map (Two Passes)

TimeO(n) SpaceO(n)

Implementation Plan

Translate the invariant into these small, testable moves.

Initialize the pointers.
Save the next node.
Rewire the current node.
Advance both pointers until the list is consumed.

def copyRandomList(head):
    oldToCopy = {None: None}
    
    curr = head
    while curr:
        copy = Node(curr.val)
        oldToCopy[curr] = copy
        curr = curr.next
        
    curr = head
    while curr:
        copy = oldToCopy[curr]
        copy.next = oldToCopy[curr.next]
        copy.random = oldToCopy[curr.random]
        curr = curr.next
        
    return oldToCopy[head]

Remove Nth Node From End of List

Add Two Numbers

Copy List with Random Pointer

Steps

Description

Constraints

Tags

Solution — Hash Map (Two Passes)