Copy List with Random Pointer

Problem

Given the head of a linked list where each node has next and random pointers (where random may point to any node in the list or null), return a deep copy of the list.

Approach

Weave clones into the original list to create an implicit mapping from original -> copy without a hash map.

1. Insert a cloned node after each original node.
2. Set each clone's random using original.random.next (the clone of original.random).
3. Detach the cloned list while restoring the original list.

Complexity

• Time: O(n)
• Space: O(1)

Solution (Java)

/*
// LeetCode provides this definition:
class Node {
    int val;
    Node next;
    Node random;
    public Node(int val) { this.val = val; }
}
*/

public class Solution {

    public Node copyRandomList(Node head) {
        boolean empty = isEmptyInput(head);
        if (empty) return returnResult(null);

        Node validatedHead = validateInput(head);

        Node wovenHead = interleaveClonesWithOriginals(validatedHead);
        Node wovenWithRandom = assignRandomPointersOnClones(wovenHead);
        Node cloneHead = detachClonedListAndRestoreOriginal(wovenWithRandom);

        return returnResult(cloneHead);
    }

    private boolean isEmptyInput(Node head) {
        return head == null;
    }

    private Node validateInput(Node head) {
        return head;
    }

    private Node interleaveClonesWithOriginals(Node headOriginal) {
        Node curr = headOriginal;
        while (curr != null) {
            Node clone = new Node(curr.val);
            Node nextOriginal = curr.next;

            curr.next = clone;
            clone.next = nextOriginal;

            curr = nextOriginal;
        }
        return headOriginal;
    }

    private Node assignRandomPointersOnClones(Node headOriginalWoven) {
        Node curr = headOriginalWoven;
        while (curr != null) {
            Node clone = curr.next;
            clone.random = (curr.random == null) ? null : curr.random.next;
            curr = clone.next;
        }
        return headOriginalWoven;
    }

    private Node detachClonedListAndRestoreOriginal(Node headOriginalWoven) {
        Node original = headOriginalWoven;
        Node cloneHead = headOriginalWoven.next;

        while (original != null) {
            Node clone = original.next;
            Node nextOriginal = clone.next;

            original.next = nextOriginal;
            clone.next = (nextOriginal == null) ? null : nextOriginal.next;

            original = nextOriginal;
        }

        return cloneHead;
    }

    private Node returnResult(Node headClone) {
        return headClone;
    }
}