Copy List With Random Pointer

NeetCode: Copy List With Random Pointer · LeetCode: 138. Copy List With Random Pointer · Difficulty: Medium

Each node has a value, a next pointer and a random pointer to any node in the list, or null. Construct a deep copy: new nodes with the same values, where every next and random pointer of the copy points to a node of the copy, never to the original.

Example

Text

values [3, 7, 4], random targets: node0 -> node2, node1 -> node0, node2 -> none
Copy: the same values and shape, made of new nodes

The node shape follows LeetCode: Node { val, next, random }. A Java variable of class type holds a reference to an object, so several pointers can target the same node, and a field holds null when it points nowhere. The fields are mutable, so a node's next can be reassigned in place. The class does not override equals or hashCode, so == and HashMap keys compare nodes by identity, not by value. Each program below builds the original list with a helper, prints (val, val of random target) for every node of the copy, and checks that the copy shares no node with the original.

Brute force: find each random target by scanning

Collect the original nodes in an ArrayList, create one copy per node, and link the copies in order. For each node's random, scan the list for the index of the target (comparing with ==) and point the copy's random at the copy with that index.

Java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Node {
    int val;
    Node next;
    Node random;

    Node(int val) {
        this.val = val;
    }
}

class Solution {
    public Node copyRandomList(Node head) {
        // Original nodes in list order.
        List<Node> originals = new ArrayList<>();
        for (Node cur = head; cur != null; cur = cur.next) {
            originals.add(cur);
        }

        // One new node per original, at the same index.
        List<Node> copies = new ArrayList<>();
        for (Node original : originals) {
            copies.add(new Node(original.val));
        }

        for (int i = 0; i < originals.size(); i++) {
            if (i + 1 < copies.size()) {
                copies.get(i).next = copies.get(i + 1);
            }
            Node target = originals.get(i).random;
            if (target != null) {
                // O(n) scan for the target's index.
                int j = 0;
                while (originals.get(j) != target) {
                    j++;
                }
                copies.get(i).random = copies.get(j);
            }
        }
        return copies.isEmpty() ? null : copies.get(0);
    }
}

public class Main {
    /** Builds a list from values and, for each node, the index of its random target (-1 for null). */
    static Node build(int[] vals, int[] randomIndex) {
        Node[] nodes = new Node[vals.length];
        for (int i = 0; i < vals.length; i++) {
            nodes[i] = new Node(vals[i]);
        }
        for (int i = 0; i < vals.length; i++) {
            if (i + 1 < nodes.length) {
                nodes[i].next = nodes[i + 1];
            }
            nodes[i].random = randomIndex[i] == -1 ? null : nodes[randomIndex[i]];
        }
        return nodes.length == 0 ? null : nodes[0];
    }

    /** Returns "(val, val of random target)" for each node, in list order. */
    static String describe(Node head) {
        List<String> parts = new ArrayList<>();
        for (Node cur = head; cur != null; cur = cur.next) {
            String target = cur.random == null ? "null" : String.valueOf(cur.random.val);
            parts.add("(" + cur.val + ", " + target + ")");
        }
        return parts.toString();
    }

    /** True if any node reachable from the copy through next or random is an original node. */
    static boolean sharesNode(Node original, Node copy) {
        Set<Node> originals = new HashSet<>();
        for (Node cur = original; cur != null; cur = cur.next) {
            originals.add(cur);
        }
        for (Node cur = copy; cur != null; cur = cur.next) {
            if (originals.contains(cur) || (cur.random != null && originals.contains(cur.random))) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Node original = build(new int[] {3, 7, 4}, new int[] {2, 0, -1});
        Node copy = new Solution().copyRandomList(original);
        System.out.println(describe(copy));
        System.out.println("shares a node? " + sharesNode(original, copy));
    }
}

Output

[(3, 4), (7, 3), (4, null)]
shares a node? false

Time: O(n^2), one O(n) scan per random pointer. Space: O(n) for the two lists (the copy itself is also O(n)).

Better: HashMap from old node to new node

The scan only answers "which copy belongs to this original?". A HashMap keyed by the original node answers it in O(1).

Pass 1: walk the list, create a copy of each node, and record original -> copy.
Pass 2: walk the list again and set each copy's next and random to the copies that the map returns for the original's next and random.

map.get(null) returns null for a HashMap, so a null next or random maps to null without a special case.

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

class Node {
    int val;
    Node next;
    Node random;

    Node(int val) {
        this.val = val;
    }
}

class Solution {
    public Node copyRandomList(Node head) {
        // Original node -> its copy.
        Map<Node, Node> copyOf = new HashMap<>();

        // Pass 1: create the copies, without any links yet.
        for (Node cur = head; cur != null; cur = cur.next) {
            copyOf.put(cur, new Node(cur.val));
        }

        // Pass 2: link each copy to the copies of the original's next and random.
        for (Node cur = head; cur != null; cur = cur.next) {
            Node copy = copyOf.get(cur);
            copy.next = copyOf.get(cur.next);
            copy.random = copyOf.get(cur.random);
        }
        return copyOf.get(head);
    }
}

public class Main {
    /** Builds a list from values and, for each node, the index of its random target (-1 for null). */
    static Node build(int[] vals, int[] randomIndex) {
        Node[] nodes = new Node[vals.length];
        for (int i = 0; i < vals.length; i++) {
            nodes[i] = new Node(vals[i]);
        }
        for (int i = 0; i < vals.length; i++) {
            if (i + 1 < nodes.length) {
                nodes[i].next = nodes[i + 1];
            }
            nodes[i].random = randomIndex[i] == -1 ? null : nodes[randomIndex[i]];
        }
        return nodes.length == 0 ? null : nodes[0];
    }

    /** Returns "(val, val of random target)" for each node, in list order. */
    static String describe(Node head) {
        List<String> parts = new ArrayList<>();
        for (Node cur = head; cur != null; cur = cur.next) {
            String target = cur.random == null ? "null" : String.valueOf(cur.random.val);
            parts.add("(" + cur.val + ", " + target + ")");
        }
        return parts.toString();
    }

    /** True if any node reachable from the copy through next or random is an original node. */
    static boolean sharesNode(Node original, Node copy) {
        Set<Node> originals = new HashSet<>();
        for (Node cur = original; cur != null; cur = cur.next) {
            originals.add(cur);
        }
        for (Node cur = copy; cur != null; cur = cur.next) {
            if (originals.contains(cur) || (cur.random != null && originals.contains(cur.random))) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Node original = build(new int[] {3, 7, 4}, new int[] {2, 0, -1});
        Node copy = new Solution().copyRandomList(original);
        System.out.println(describe(copy));
        System.out.println("shares a node? " + sharesNode(original, copy));
    }
}

Output

[(3, 4), (7, 3), (4, null)]
shares a node? false

Time: O(n). Space: O(n) for the map.

Optimal: interleave the copies, then split

The map can be replaced by the list itself: put each copy directly after its original, so the copy of any node is node.next.

Text

A -> B -> C            becomes      A -> A' -> B -> B' -> C -> C'

Insert a copy after every original node (A -> A' -> B -> B' -> ...).
For every original X with X.random = R, set X'.random = R', which is R.next.
Split the interleaved list back into the original list and the copy list, restoring the original next pointers.

Java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Node {
    int val;
    Node next;
    Node random;

    Node(int val) {
        this.val = val;
    }
}

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null; // empty list: nothing to copy
        }

        // Step 1: A -> B  becomes  A -> A' -> B -> B'
        for (Node cur = head; cur != null; ) {
            Node copy = new Node(cur.val);
            copy.next = cur.next; // the copy points to the next original
            cur.next = copy;      // the original points to its copy
            cur = copy.next;
        }

        // Step 2: the copy's random is the node right after the original's random.
        for (Node cur = head; cur != null; cur = cur.next.next) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
        }

        // Step 3: split A -> A' -> B -> B' back into A -> B and A' -> B'.
        Node newHead = head.next;
        for (Node cur = head; cur != null; ) {
            Node copy = cur.next;
            cur.next = copy.next; // restore the original list
            copy.next = copy.next == null ? null : copy.next.next; // link the copies together
            cur = cur.next;
        }
        return newHead;
    }
}

public class Main {
    /** Builds a list from values and, for each node, the index of its random target (-1 for null). */
    static Node build(int[] vals, int[] randomIndex) {
        Node[] nodes = new Node[vals.length];
        for (int i = 0; i < vals.length; i++) {
            nodes[i] = new Node(vals[i]);
        }
        for (int i = 0; i < vals.length; i++) {
            if (i + 1 < nodes.length) {
                nodes[i].next = nodes[i + 1];
            }
            nodes[i].random = randomIndex[i] == -1 ? null : nodes[randomIndex[i]];
        }
        return nodes.length == 0 ? null : nodes[0];
    }

    /** Returns "(val, val of random target)" for each node, in list order. */
    static String describe(Node head) {
        List<String> parts = new ArrayList<>();
        for (Node cur = head; cur != null; cur = cur.next) {
            String target = cur.random == null ? "null" : String.valueOf(cur.random.val);
            parts.add("(" + cur.val + ", " + target + ")");
        }
        return parts.toString();
    }

    /** True if any node reachable from the copy through next or random is an original node. */
    static boolean sharesNode(Node original, Node copy) {
        Set<Node> originals = new HashSet<>();
        for (Node cur = original; cur != null; cur = cur.next) {
            originals.add(cur);
        }
        for (Node cur = copy; cur != null; cur = cur.next) {
            if (originals.contains(cur) || (cur.random != null && originals.contains(cur.random))) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Node original = build(new int[] {3, 7, 4}, new int[] {2, 0, -1});
        Node copy = new Solution().copyRandomList(original);
        System.out.println(describe(copy));
        System.out.println(describe(original));
        System.out.println("shares a node? " + sharesNode(original, copy));
    }
}

Output

[(3, 4), (7, 3), (4, null)]
[(3, 4), (7, 3), (4, null)]
shares a node? false

Time: O(n), three passes. Space: O(1) extra, not counting the copy itself.

The method restores the original list, so the caller's nodes end up with the same next and random values as before. Random pointers that form cycles are not a problem in Java: the garbage collector reclaims objects that nothing reachable refers to, including cycles.

Edge cases

An empty list returns null.
A random pointer can be null, point to the node itself, or point backwards or forwards.
In the interleaving version, step 2 must finish before step 3, because step 2 relies on R.next being the copy of R.

How to explain it in an interview

The difficulty is random: when a copy is created, its target's copy may not exist yet.
Brute force: create the copies, then find each target's index by scanning, O(n^2).
Hash map: map each original to its copy in one pass, wire next and random in a second pass, O(n) time and space.
Interleaving: place each copy right after its original, so the copy of any node is node.next. No map is needed.
Three passes: insert copies, set random with original.random.next, then split the two lists apart. O(n) time, O(1) extra space.