☕ DSA Java Articles

Topics › Linked List › Hard Problems of LL

Clone a LL with random and next pointer

Hard TUF ID 611 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the head of a linked list in which every node has a value, a next pointer, and an extra random pointer that may point to any node in the list or be null. Build a deep copy of the list: a new list with the same values, whose next and random pointers point to the corresponding new nodes. No pointer in the copy may refer to a node of the original, and the original list must be left unchanged. Return the head of the copy.

Constraints: 0 ≤ n ≤ 1000, values fit in an int, every random is null or a node of the same list.

Example 1

original: 7 -> 13 -> 11 -> 10 -> 1
random:   null, 7, 1, 11, 7        // 13.random = 7, 11.random = 1, 10.random = 11, 1.random = 7
answer:   a new list 7 -> 13 -> 11 -> 10 -> 1 with the same random structure among the new nodes

Example 2

original: 1 -> 2
random:   2, 1                     // the randoms cross
answer:   new nodes 1' -> 2' with 1'.random = 2' and 2'.random = 1'

Example 3

original: 3 -> 3 -> 3
random:   null, first 3, null
answer:   a copy where the second node's random points to the first copied node, not merely to "some node with value 3"

Example 3 is the crux. Values can repeat, so a copy’s random cannot be found by searching for a value. We need a way to go from an original node to its own copy, by identity.

Approach 1: Brute force, locate randoms by position

Intuition. Copy the values and next pointers first; that is an ordinary list copy. Then, for each original node whose random is set, work out the position of the target in the original list by walking from the head and counting, and walk the same number of steps in the copy. Position is an identity that survives copying, even when values repeat.

Algorithm.

  1. If the list is empty return null.
  2. First pass: for each original node create a copy with the same value and link the copies through next.
  3. Second pass, walking original and copy in step: if orig.random is set, count the steps pos from head to orig.random, then walk pos steps from copyHead and assign that node to copy.random.
  4. Return copyHead.
static Node bruteForce(Node head) {
    if (head == null) return null;
    Node copyHead = new Node(head.val), copyTail = copyHead;          // pass 1: values and next pointers
    for (Node t = head.next; t != null; t = t.next) {
        copyTail.next = new Node(t.val);
        copyTail = copyTail.next;
    }
    Node orig = head, copy = copyHead;                                 // pass 2: random pointers by position
    while (orig != null) {
        if (orig.random != null) {
            int pos = 0;
            for (Node t = head; t != orig.random; t = t.next) pos++;   // index of the random target in the original list
            Node target = copyHead;
            for (int i = 0; i < pos; i++) target = target.next;        // the node at the same index in the copy
            copy.random = target;
        }
        orig = orig.next;
        copy = copy.next;
    }
    return copyHead;
}

Complexity. Time O(n^2): for each of n nodes the position search can take up to n steps. Space O(1) beyond the n new nodes that any solution must create.

The comparison t != orig.random is a reference comparison, which is exactly what we want: it finds that node, not a node with an equal value. The quadratic cost comes from recomputing positions from scratch each time; the next approach remembers the correspondence instead.

Approach 2: Better, hash map from original to copy

Intuition. The brute force is slow because “which copy corresponds to this original?” is answered by a linear search. Store the answer in a HashMap<Node, Node> instead. One pass creates a copy for every original and records the pairing; a second pass sets copy.next = map(orig.next) and copy.random = map(orig.random). Because Node does not override equals, the map keys are compared by identity, so repeated values are never confused.

Algorithm.

  1. For each original node t, put t -> new Node(t.val) into the map.
  2. For each original node t, let copy = map.get(t); set copy.next = map.get(t.next) and copy.random = map.get(t.random).
  3. Return map.get(head).
static Node better(Node head) {
    Map<Node, Node> copyOf = new HashMap<>();
    for (Node t = head; t != null; t = t.next) copyOf.put(t, new Node(t.val));
    for (Node t = head; t != null; t = t.next) {
        Node copy = copyOf.get(t);
        copy.next = copyOf.get(t.next);          // get(null) is null, so the tail needs no special case
        copy.random = copyOf.get(t.random);
    }
    return copyOf.get(head);
}

Complexity. Time O(n): two passes with constant-time map operations on average. Space O(n) for the map, on top of the copy itself.

HashMap.get(null) returns null, which neatly handles both the tail’s next and any null random without branching, and copyOf.get(head) returns null for an empty list. This is the version to write first in an interview: short, obviously correct, and linear. The follow-up question is always “can you do it without the map?”

Approach 3: Optimal, interleave the copies

Intuition. The map’s only job is to get from an original node to its copy. We can encode that relationship in the list itself: insert each copy immediately after its original, producing A -> A' -> B -> B' -> .... Now the copy of any node X is simply X.next, so A'.random = A.random.next, with no lookup structure at all. A final pass unzips the interleaved list into the original and the copy, restoring the original’s next pointers.

Algorithm.

  1. Pass 1: for each original t, create copy with t.val, set copy.next = t.next and t.next = copy. Advance with t = t.next.next to skip the copy just inserted.
  2. Pass 2: for each original t (again stepping by two), if t.random is set, assign t.next.random = t.random.next.
  3. Pass 3: remember copyHead = head.next. For each original t, let copy = t.next; set t.next = copy.next (the next original) and copy.next = copy.next == null ? null : copy.next.next (the next copy).
  4. Return copyHead.
static Node optimal(Node head) {
    if (head == null) return null;
    for (Node t = head; t != null; t = t.next.next) {        // step 1: insert a copy after every original
        Node copy = new Node(t.val);
        copy.next = t.next;
        t.next = copy;
    }
    for (Node t = head; t != null; t = t.next.next) {        // step 2: the copy's random is the copy of the original's random
        if (t.random != null) t.next.random = t.random.next;
    }
    Node copyHead = head.next;
    for (Node t = head; t != null; t = t.next) {             // step 3: separate the two lists, restoring the original
        Node copy = t.next;
        t.next = copy.next;
        copy.next = (copy.next != null) ? copy.next.next : null;
    }
    return copyHead;
}

Dry run on 1 -> 2 with 1.random = 2, 2.random = 1:

step list randoms set
after pass 1 1 -> 1’ -> 2 -> 2’ none on copies yet
pass 2 at 1   1’.random = 1.random.next = 2.next = 2’
pass 2 at 2   2’.random = 2.random.next = 1.next = 1’
pass 3 1 -> 2 and 1’ -> 2’  

The copy 1' -> 2' has crossing randoms among the new nodes, and the original is back to 1 -> 2.

Complexity. Time O(n): three linear passes. Space O(1) extra: the only allocations are the n copied nodes that form the answer.

Why does t = t.next.next never throw in passes 1 and 2? During pass 1, after inserting the copy, t.next is the copy and t.next.next is the next original or null. During pass 2 the interleaving is complete, so every original has a copy after it. In pass 3 we step with t = t.next because by the time the step executes, t.next has already been restored to the next original.

Why is t.random.next the right copy? Because t.random is some original node X, and after pass 1 the node right after every original is its own copy. This is the single observation that replaces the whole hash map.

Edge cases and pitfalls