LeetCode 138 · Linked List

Copy List with Random Pointer, explained with a picture

Photocopying a train with buddy links.

MediumLinked List
▶ Watch it step by step

The problem

Each node in a linked list has a next pointer and a random pointer that can point to any node or to nothing. Make a deep copy: brand-new nodes whose next and random links mirror the original.

Input:  values [7, 13, 11, 10, 1], random → [none, 0, 4, 2, 0]
Output: an identical new list (no node shared with the original)

Picture it

Picture a train where each coach also has a buddy link to some other coach. We want to photocopy the whole train. First pass: build a copy of every coach and note in a lookup table “original → copy”. Second pass: for each original coach, wire its copy’s next and buddy to the copies of its next and buddy, found via the table.

How to recognise it

  • You must build a deep copy: brand-new nodes, none shared with the original, wired exactly the same way.
  • Some links can point anywhere, including backwards or to nodes not created yet, so you cannot wire everything in one forward walk.
  • Values may repeat, so a node cannot be identified by its value. You need to identify nodes by identity (which object they are).
  • When the question is "for this original node, which copy belongs to it?", a dictionary from old node to new node answers it in O(1). The same idea clones graphs.

Start with brute force

Copy the next chain first. Then, for each random pointer, find its target's position by walking the original list from the head, and walk the copy the same number of steps.

def copy_random_brute(head):
    dummy = tail = Node(0)
    node = head
    while node:                      # copy values and next links
        tail.next = Node(node.val)
        tail, node = tail.next, node.next
    node, copy = head, dummy.next
    while node:
        if node.random:
            target, i = head, 0      # position of node.random
            while target is not node.random:
                target, i = target.next, i + 1
            other = dummy.next       # same position in the copy
            for _ in range(i):
                other = other.next
            copy.random = other
        node, copy = node.next, copy.next
    return dummy.next

Each random pointer can cost two walks of up to n steps, so time is O(n²) and extra space O(1) beyond the copy. LeetCode allows 1,000 nodes, about 10^6 steps, which still passes, but a list of 10^5 nodes would need about 10^10.

From brute force to the idea

  1. Find the waste. Both inner walks answer one question: "which copy belongs to this original node?" The brute force recomputes it from the head every time.
  2. Remember the answer. Store it once in a dictionary clone that maps each original node to its copy. Python dictionaries can use node objects as keys; they are compared by identity, so repeated values are no problem.
  3. First pass: make the nodes. Walk the list and create clone[node] = Node(node.val), with no links yet. Now every copy exists, even ones a random pointer will need later.
  4. Second pass: wire the links. For each original node, clone[node].next = clone[node.next] and clone[node].random = clone[node.random].
  5. Handle None with one entry. The dictionary starts as {None: None}, so a missing next or random maps to None without an if. It also makes clone[head] return None for an empty list.

This is the key idea: a dictionary from original node to copy, filled in one pass and used to wire every pointer in a second.

The key idea

A dictionary from old node to new node lets you wire every pointer in a second pass. O(n).

Python solution

def copy_random(head):
    clone = {None: None}
    node = head
    while node:
        clone[node] = Node(node.val)
        node = node.next
    node = head
    while node:
        clone[node].next = clone[node.next]
        clone[node].random = clone[node.random]
        node = node.next
    return clone[head]

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n²): up to two walks of n steps per random pointerO(1) beyond the n new nodes
Dictionary, two passes (shown code)O(n): each pass visits every node once, lookups are O(1) on averageO(n): the dictionary holds one entry per node (plus the n new nodes)

Edge cases

  • Empty list: both loops are skipped and clone[None] returns None.
  • Random pointing to itself: clone[node].random = clone[node], so the copy points to itself, not to the original.
  • Random is None: handled by the {None: None} entry, no check needed.
  • Repeated values ([1, 1], each random pointing to the other): works, because the keys are the node objects, not their values.
  • Random pointing forwards: fine, since every copy was created in the first pass before any wiring.
  • The original is untouched: the shown code only reads the input, so the original list keeps all its links.

Common mistakes

  • Writing clone[node].random = node.random. The copy then points into the original list, which is not a deep copy.
  • Keying the dictionary by node.val. Two nodes with the same value overwrite each other's copy.
  • Wiring random during the first pass, before the target's copy exists, which raises KeyError.
  • Forgetting the None entry, so the last node's clone[node.next] raises KeyError.
Your turn: copy with O(1) extra space

Make the same deep copy without a dictionary, using only O(1) extra space besides the new nodes. The original list must be unchanged afterwards. Describe your approach, then write it if you like.

Compare with our answer

Use the list itself as the lookup table. Insert each copy right after its original (A → A′ → B → B′). Then the copy of any node X is simply X.next, so the copy's random is node.random.next. Finally, unweave the two lists, restoring the original links.

def copy_random_weave(head):
    node = head
    while node:                          # 1. A -> A' -> B -> B' ...
        node.next = Node(node.val, node.next)
        node = node.next.next
    node = head
    while node:                          # 2. copy of random is random.next
        if node.random:
            node.next.random = node.random.next
        node = node.next.next
    dummy = tail = Node(0)
    node = head
    while node:                          # 3. unweave, restoring the original
        copy = node.next
        node.next = copy.next
        tail.next = copy
        tail = copy
        node = node.next
    return dummy.next

Time O(n), extra space O(1) besides the copy.

A strong answer mentions: interleaving so that X.next is X's copy, setting all randoms before unweaving, and restoring the original next links.

Check what stuck

1. You must deep-copy a graph where each node has a list of neighbours, and cycles are possible. Which approach fits best?

2. Why does the shown code start the dictionary as {None: None}?

3. A learner writes clone[node].random = node.random in the second loop. What is wrong with the result?

Score 60% or more and the lesson is marked complete.