The algorithm works in three phases:

1. Duplicate each node and insert it immediately after its original
2. Copy the random pointers from original nodes to their duplicates
3. Separate the interleaved lists into original and copy

C++ Implementation

class LinkedListCloner {
public:
    Node* cloneList(Node* head) {
        if (!head) return nullptr;
        
        // Phase 1: Create interleaved nodes
        Node* current = head;
        while (current) {
            Node* duplicate = new Node(current->value);
            duplicate->next = current->next;
            current->next = duplicate;
            current = duplicate->next;
        }
        
        // Phase 2: Set random pointers
        current = head;
        while (current) {
            if (current->random) {
                current->next->random = current->random->next;
            }
            current = current->next->next;
        }
        
        // Phase 3: Separate lists
        Node* clonedHead = head->next;
        Node* original = head;
        Node* cloned = clonedHead;
        
        while (cloned->next) {
            original->next = cloned->next;
            original = original->next;
            cloned->next = original->next;
            cloned = cloned->next;
        }
        original->next = nullptr;
        
        return clonedHead;
    }
};

Java Implementation

class LinkedListDuplicator {
    public Node duplicateList(Node head) {
        if (head == null) return null;
        
        // Create interleaved nodes
        Node iterator = head;
        while (iterator != null) {
            Node copy = new Node(iterator.val);
            copy.next = iterator.next;
            iterator.next = copy;
            iterator = copy.next;
        }
        
        // Copy random references
        iterator = head;
        while (iterator != null) {
            if (iterator.random != null) {
                iterator.next.random = iterator.random.next;
            }
            iterator = iterator.next.next;
        }
        
        // Separate the lists
        Node cloned = head.next;
        Node original = head;
        Node result = cloned;
        
        while (cloned.next != null) {
            original.next = cloned.next;
            original = original.next;
            cloned.next = original.next;
            cloned = cloned.next;
        }
        original.next = null;
        
        return result;
    }
}