LeetEye LeetEye
Medium Linked List ~5 min

Copy List with Random Pointer

linked-list copy-list-with-random-pointer

Problem

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state.

Return the head of the copied linked list.

Examples

Example 1
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Key Insight

Map old nodes to new nodes. When setting random pointers, look up the corresponding new node.

Challenge: random points to not-yet-created nodes. Solution: create all nodes first (map them), then set pointers. Or interleave for O(1) space.

How to Approach This Problem

Pattern Recognition: When you see keywords like copy list with random pointer linked-list, think Linked List.

Step-by-Step Reasoning

1 Simply creating nodes as we traverse fails because:
Answer: Random might point to a node not yet created
If node 1's random points to node 5, when we're at node 1, node 5's copy doesn't exist yet.
2 Using a hash map {old_node: new_node} helps because:
Answer: We can look up corresponding new node for any old node
When setting random, we find old_node's random in the map to get the new target.
3 Interleaving means placing each new node:
Answer: Right after its corresponding old node
old1 → new1 → old2 → new2 → ... This lets us access new nodes without a map.
4 With interleaving, if old.random = X, then new.random should be:
Answer: X.next
X.next is the new copy of X (due to interleaving). So old.random.next = corresponding new node.
5 After setting all pointers, we need to:
Answer: Separate the lists (restore original and extract copy)
We need to return a clean copy and restore the original list to its state.

Solution

def copyRandomList(head: Node) -> Node:
    if not head:
        return None
    
    # Map old nodes to new nodes
    old_to_new = {}
    
    # First pass: create all new nodes
    curr = head
    while curr:
        old_to_new[curr] = Node(curr.val)
        curr = curr.next
    
    # Second pass: set next and random pointers
    curr = head
    while curr:
        old_to_new[curr].next = old_to_new.get(curr.next)
        old_to_new[curr].random = old_to_new.get(curr.random)
        curr = curr.next
    
    return old_to_new[head]

Complexity Analysis

Time O(n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Linked List problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye