Copy List with Random Pointer

MediumLinked List · Hash Map · Interleaving🧩 Linked List Techniques LeetCode #138 ↗Updated Oct 30, 2026

Problem

Each node of a linked list has a next pointer and an extra random pointer that may point to any node of the list or to null. Build a deep copy: brand-new nodes with the same values whose next and random pointers mirror the original structure but point only to new nodes. Return the head of the copy; the original list must stay unchanged.

Input[[7,null],[13,0],[11,4],[10,2],[1,0]] ([val, random index])Outputsame shape, all new nodes

Input[[1,1],[2,1]]Output[[1,1],[2,1]]

Input[]Output[]

0 ≤ n ≤ 1000 · -10⁴ ≤ Node.val ≤ 10⁴ · random is null or a node in the list

Try it yourself

Java

class Solution {
    public Node copyRandomList(Node head) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The hard part is translating “original node → its copy” for random. A hash map does it in O(1); or, for O(1) extra space, place each copy right after its original so the copy of x is just x.next.

PatternLinked List Techniques

Instinct Nodes joined by next pointers and the task is to reverse, splice, merge, reorder or remove in place - grab a dummy head and rewire pointers carefully.

Memory hack Save next, flip, step - never let go of a rope before you've grabbed the next one.

Open the Linked List Techniques guide →

Approaches

Brute ForceCopy by Index, Linear Search for Random

Time O(n²)Space O(n)

Copy the nodes in order into a list and chain them. For each original random, find its position by scanning the original list (by identity, since values can repeat), then point the copy at the copy with the same position.

Java

public Node copyRandomList(Node head) {
    List<Node> olds = new ArrayList<>(), copies = new ArrayList<>();
    for (Node c = head; c != null; c = c.next) {
        olds.add(c);
        copies.add(new Node(c.val));
    }
    for (int i = 0; i < copies.size(); i++) {
        if (i + 1 < copies.size()) copies.get(i).next = copies.get(i + 1);
        Node target = olds.get(i).random;
        if (target == null) continue;
        int j = 0;
        while (olds.get(j) != target) j++; // compare references, not values
        copies.get(i).random = copies.get(j);
    }
    return copies.isEmpty() ? null : copies.get(0);
}

Simple bookkeeping, but each random lookup is a linear scan.

BetterHash Map: Original → Copy

Time O(n)Space O(n)

First pass: create a copy of every node and store map[original] = copy. Second pass: wire each copy with map.get(orig.next) and map.get(orig.random) — get(null) conveniently returns null.

Java

public Node copyRandomList(Node head) {
    Map<Node, Node> copyOf = new HashMap<>();
    for (Node c = head; c != null; c = c.next) copyOf.put(c, new Node(c.val));
    for (Node c = head; c != null; c = c.next) {
        Node copy = copyOf.get(c);
        copy.next = copyOf.get(c.next);     // null maps to null
        copy.random = copyOf.get(c.random);
    }
    return copyOf.get(head);
}

Clean and linear — usually enough unless O(1) space is asked.

OptimalInterleave Copies, Wire Random, Split

Time O(n)Space O(1) extra

1) Insert each copy right after its original: A → A' → B → B'. 2) Now copy(x) = x.next, so x.next.random = x.random.next. 3) Unweave the two lists, restoring the original next pointers.

Java

public Node copyRandomList(Node head) {
    if (head == null) return null;
    for (Node c = head; c != null; c = c.next.next) { // 1) A -> A' -> B -> B'
        Node copy = new Node(c.val);
        copy.next = c.next;
        c.next = copy;
    }
    for (Node c = head; c != null; c = c.next.next) { // 2) wire random pointers
        if (c.random != null) c.next.random = c.random.next;
    }
    Node newHead = head.next;
    for (Node c = head; c != null; c = c.next) {      // 3) split the lists
        Node copy = c.next;
        c.next = copy.next;
        copy.next = copy.next == null ? null : copy.next.next;
    }
    return newHead;
}

Linear time with no map — the follow-up answer interviewers look for.

Pro tip

Do the random pass before splitting — once the lists are separated, x.random.next no longer points to the copy.

At a glance

Level	Approach	Time	Space
Brute Force	Copy by Index, Linear Search for Random	`O(n²)`	`O(n)`
Better	Hash Map: Original → Copy	`O(n)`	`O(n)`
Optimal	Interleave Copies, Wire Random, Split	`O(n)`	`O(1) extra`

Common pitfalls

Copying random as-is — the copy then points into the original list.
Finding random targets by value — values can repeat.
Forgetting to restore the original's next pointers in the interleaving method.

Interview tips

Clarify “deep copy”: no node of the result may be shared with the input.
Lead with the hash map, then offer interleaving when asked for O(1) space.
Draw the interleaved list; x.random.next is the whole trick.

Pattern

Old → new node mapping (map or interleave) → clone a linked structure with extra pointers.

My notes saved in this browser