Clone a linked list with next and random pointer

GeeksforGeeks

???? Problem:

You are given a linked list where each node has a next pointer and a random pointer. The task is to clone the list such that both the next and random pointers of the new nodes point to the corresponding nodes in the copied list, with no reference to the original list.

?? Example:

• Input: LinkedList: 1 → 2 → 3 → 4, Random Pointers = [{1,2}, {2,4}]
• Output: A new cloned list with the same structure and random pointers.

?? Approach:

To solve this problem efficiently with O(n) time complexity and O(1) space complexity, we'll adopt a three-step approach:

1. Step 1: Duplicate Nodes Insert a copy of each node right after the original node in the linked list. This will help us manage both next and random pointers later.
2. Step 2: Fix Random Pointers For each new node, set its random pointer to the corresponding new node using the original list's random pointers.
3. Step 3: Separate the Lists Finally, split the combined linked list into two separate lists: one is the original, and the other is the newly copied list.

?? Sample Code:

class Node {
    int data;
    Node next, random;

    Node(int d) {
        data = d;
        next = random = null;
    }
}

class Solution {
    // Function to clone a linked list with next and random pointer.
    Node copyList(Node head) {
        if (head == null) return null;

        // Step 1: Insert copy nodes
        Node curr = head;
        while (curr != null) {
            Node newNode = new Node(curr.data);
            newNode.next = curr.next;
            curr.next = newNode;
            curr = newNode.next;
        }

        // Step 2: Fix random pointers
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }

        // Step 3: Separate the lists
        curr = head;
        Node copyHead = head.next;
        Node copy = copyHead;
        while (curr != null) {
            curr.next = curr.next.next;
            if (copy.next != null) {
                copy.next = copy.next.next;
            }
            curr = curr.next;
            copy = copy.next;
        }

        return copyHead;
    }
}        

?? Time Complexity:

• O(n) because we traverse the linked list multiple times but still in a linear fashion.

?? Summary:

Using a three-step approach (duplicating nodes, setting random pointers, and separating the lists), we achieve a cloned linked list in optimal time and space complexity. The beauty of this approach is its space efficiency, with O(1) extra space being used!