Clone a Linked List with Random Pointers: Deep Dive with All 3 Approaches

package io.thecodeforge.list;

import java.util.HashMap;
import java.util.Map;

/**
 * Deep clone a linked list with random pointers.
 * HashMap approach: O(n) time, O(n) space.
 * Weaving approach: O(n) time, O(1) space.
 */
public class CloneLinkedListWithRandom {

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

        Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    // ─── Approach 1: HashMap (O(n) space) ──────────────────────────────────
    public static Node cloneWithHashMap(Node head) {
        if (head == null) return null;

        // Pass 1: create all clone nodes, store mapping original -> clone
        Map<Node, Node> cloneMap = new HashMap<>();
        Node current = head;
        while (current != null) {
            cloneMap.put(current, new Node(current.val));
            current = current.next;
        }

        // Pass 2: wire next and random pointers using the map
        current = head;
        while (current != null) {
            cloneMap.get(current).next = cloneMap.get(current.next);
            cloneMap.get(current).random = cloneMap.get(current.random);
            current = current.next;
        }

        return cloneMap.get(head);
    }

    // ─── Approach 2: Weaving (O(1) space) ──────────────────────────────────
    public static Node cloneWithWeaving(Node head) {
        if (head == null) return null;

        // Step 1: Interleave — insert clone after each original
        // Original: A -> B -> C
        // After:    A -> A' -> B -> B' -> C -> C'
        Node current = head;
        while (current != null) {
            Node clone = new Node(current.val);
            clone.next = current.next;
            current.next = clone;
            current = clone.next;
        }

        // Step 2: Set random pointers
        // A'.random = A.random.next (the clone of A's random target)
        current = head;
        while (current != null) {
            if (current.random != null) {
                current.next.random = current.random.next;
            }
            current = current.next.next;
        }

        // Step 3: Un-weave — separate original and clone lists
        Node cloneHead = head.next;
        current = head;
        while (current != null) {
            Node clone = current.next;
            current.next = clone.next;
            clone.next = (clone.next != null) ? clone.next.next : null;
            current = current.next;
        }

        return cloneHead;
    }

    // ─── Verification ──────────────────────────────────────────────────────
    public static boolean verifyClone(Node original, Node clone) {
        // Verify no original nodes are reachable from the clone
        // by checking identity hashes don't overlap
        Node origCurrent = original;
        Node cloneCurrent = clone;

        while (origCurrent != null && cloneCurrent != null) {
            if (origCurrent == cloneCurrent) return false; // same object
            if (cloneCurrent.random != null && cloneCurrent.random == origCurrent) return false;
            origCurrent = origCurrent.next;
            cloneCurrent = cloneCurrent.next;
        }
        return cloneCurrent == null && origCurrent == null; // same length
    }

    public static void main(String[] args) {
        // Build: 1 -> 2 -> 3
        // Random: 1->3, 2->1, 3->2
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        n1.next = n2; n2.next = n3;
        n1.random = n3; n2.random = n1; n3.random = n2;

        // Clone with HashMap
        Node clone1 = cloneWithHashMap(n1);
        System.out.println("HashMap clone:");
        System.out.println("  Values: " + clone1.val + " -> " + clone1.next.val + " -> " + clone1.next.next.val);
        System.out.println("  Random: 1->" + clone1.random.val + ", 2->" + clone1.next.random.val + ", 3->" + clone1.next.next.random.val);
        System.out.println("  Independent: " + verifyClone(n1, clone1));
        System.out.println("  Identity diff: " + (clone1 != n1 && clone1.random != n1.random));

        // Clone with weaving
        Node clone2 = cloneWithWeaving(n1);
        System.out.println("\nWeaving clone:");
        System.out.println("  Values: " + clone2.val + " -> " + clone2.next.val + " -> " + clone2.next.next.val);
        System.out.println("  Random: 1->" + clone2.random.val + ", 2->" + clone2.next.random.val + ", 3->" + clone2.next.next.random.val);
        System.out.println("  Independent: " + verifyClone(n1, clone2));

        // Edge case: null list
        Node nullClone = cloneWithHashMap(null);
        System.out.println("\nNull list clone: " + (nullClone == null ? "null" : "ERROR"));

        // Edge case: single node with self-random
        Node self = new Node(42);
        self.random = self;
        Node selfClone = cloneWithHashMap(self);
        System.out.println("Self-random clone: val=" + selfClone.val + ", random->val=" + selfClone.random.val + ", isSameObject=" + (selfClone == selfClone.random));
    }
}