Copy List with Random Pointer

Medium Linked List Miscellaneous Original on LeetCode

Copy List with Random Pointer is a medium linked list problem solved with the miscellaneous pattern. The best approach, optimal (interleave copies in the list), runs in O(n) time and O(1) space. Below are 2 approaches in Java, from hash map from original to copy up.

Problem

Each node of a linked list has a next pointer and a random pointer that can point to any node in the list or be null. Build a deep copy: brand-new nodes whose next and random pointers mirror the original structure. No pointer in the copy may point into the original list.

Examples

Example 1

Input: head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]
Output: a deep copy with the same structure
Why: Each pair is [value, index that random points to].

Example 2

Input: head = []
Output: []

Constraints

The list has 0 to 1000 nodes.
random can point to any node or be null.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Hash map from original to copy	`O(n)`	`O(n)`
Optimal (interleave copies in the list)	`O(n)`	`O(1)`

1Hash map from original to copy

TimeO(n)

SpaceO(n)

First pass: create a copy of every node and store original → copy. Second pass: set each copy's next and random using the map.

map.put(node, new Node(node.val)) for every node.
copy.next = map.get(node.next); copy.random = map.get(node.random).

Java

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        for (Node p = head; p != null; p = p.next) map.put(p, new Node(p.val));
        for (Node p = head; p != null; p = p.next) {
            map.get(p).next = map.get(p.next);
            map.get(p).random = map.get(p.random);
        }
        return map.get(head);
    }
}

2Optimal (interleave copies in the list)

TimeO(n)

SpaceO(1)No map; only the copies themselves, which are the output.

Insert each copy right after its original: A → A' → B → B'. Then A'.random = A.random.next. Finally split the two interleaved lists apart.

Pass 1: insert copies after each node.
Pass 2: copy.random = orig.random == null ? null : orig.random.next.
Pass 3: restore originals and link the copies together.

Java

class Solution {
    public Node copyRandomList(Node head) {
        for (Node p = head; p != null; p = p.next.next) {
            Node c = new Node(p.val);
            c.next = p.next;
            p.next = c;
        }
        for (Node p = head; p != null; p = p.next.next)
            if (p.random != null) p.next.random = p.random.next;
        Node dummy = new Node(0), tail = dummy;
        for (Node p = head; p != null; p = p.next) {
            Node c = p.next;
            p.next = c.next;
            tail.next = c;
            tail = c;
        }
        return dummy.next;
    }
}

Edge cases to test

random points to itself
random is null
Empty list

Hints

Hint 1

You need a mapping from each original node to its copy. Can the copy live right after the original in the list itself?

FAQ

What is the best time complexity for Copy List with Random Pointer?

Optimal (interleave copies in the list) runs in O(n) time and O(1) extra space.

Which pattern does Copy List with Random Pointer use?

It is a linked list problem that uses the miscellaneous pattern. Other problems with the same pattern: Delete Node in a Linked List, Intersection of Two Linked Lists, Partition List.

Is there a brute force solution for Copy List with Random Pointer?

Yes. Hash map from original to copy takes O(n) time and O(n) space. First pass: create a copy of every node and store original → copy.

Which edge cases should I test for Copy List with Random Pointer?

random points to itself; random is null; Empty list.