Clone a linked list with next and random pointer

The problem, simply

Every box in this linked list has two arrows. next points to the box after it, as usual. random can point to any box in the list, or to null.

Build a deep copy: brand new boxes with the same numbers, where the new next and random arrows point to the new boxes in the same pattern. No arrow in the copy may point back into the original list. Return the head of the copy, and leave the original list as it was.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep a notebook that says "the copy of this old box is that new box", a hash map.

1. Walk the list. For each old box, make a new box with the same number and write the pair in the map.
2. Walk again. For each old box p, set copy(p).next = copy(p.next) and copy(p).random = copy(p.random), looking both up in the map.
3. Return copy(head).

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

How long it takes: two walks, O(n). Extra room: the map holds a pair for every box, O(n).

Way 2: the clever way

Use the line trick. Each new box stands right after its old twin, so the list itself becomes the notebook: the copy of any old box x is x.next.

1. Weave: for each old box, make its copy and slip it in right after it.
2. Randoms: for each old box p with a random, set p.next.random = p.random.next. That reads: my copy's random is the copy of my random.
3. Unzip: walk the woven list and split it back into the old list and the new list.

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        for (Node p = head; p != null; p = p.next.next) {      // 1. weave each copy in
            Node copy = new Node(p.val);
            copy.next = p.next;
            p.next = copy;
        }
        for (Node p = head; p != null; p = p.next.next) {      // 2. copy of my random
            if (p.random != null) p.next.random = p.random.next;
        }
        Node copyHead = head.next;
        for (Node p = head; p != null; p = p.next) {           // 3. unzip
            Node copy = p.next;
            p.next = copy.next;
            copy.next = (copy.next != null) ? copy.next.next : null;
        }
        return copyHead;
    }
}

How long it takes: three walks, O(n). Extra room: no map, only fingers, O(1) besides the copy itself.

Watch out for

• Setting randoms during the unzip. Randoms can point backwards, to boxes already unzipped, where x.next is no longer the copy. Finish all randoms before you unzip.
• Forgetting p.random != null. A null random has no .next.
• Not restoring the original. The problem says to leave it as it was, so the unzip must fix the old next arrows too.
• In the weave loop, stepping p = p.next instead of p.next.next lands on the copy you just made and loops forever.

What interviewers ask next

• Clone a graph (LeetCode 133). Same map idea, with a breadth first or depth first walk, because a graph has no single line to weave into.
• Clone a binary tree with random pointers. Use the map, or weave copies in as the left child of each node, then unzip.
• Can you do it in one pass with the map? Yes. Walk once and create twins lazily: when you need the copy of a box that is not in the map yet, make it then.
• Why is Way 2 only O(1) extra room? The copy itself must be built anyway. Besides it, Way 2 keeps only a few fingers, while Way 1 keeps a map of n pairs.

Remember this

Grown-up words: buddy cards are random pointers, a twin made of new boxes is a deep copy, the notebook is a hash map from old node to new node, and standing behind your twin is interleaving the lists.