# Clone a linked list with next and random pointer in Java

A linked list with next and random pointer is a data structure where each node contains two pointers: one pointing to the next node in the sequence and another pointing to a random node in the list. These random pointers can reference any node in the list, including itself or null. Its design allows the creation of a clone of the original linked list while maintaining both the sequential and random relationships between nodes.

Example:

Clone a Linked List with next and Random Pointer using Extra Space

Cloning a linked list with next and random pointers using extra space involves creating a duplicate of each node while maintaining the relationships between nodes. By storing mappings between original and cloned nodes, this approach ensures accurate replication of both sequential and random connections within the list.

## Approach: Using HashMap

### Algorithm

Step 1: Create a HashMap to store mappings between original and cloned nodes.
Step 2: Traverse the original linked list, creating a new node for each original node and store the mapping in the HashMap.

Step 3: Iterate through the original list again and set the next pointers of cloned nodes based on mappings stored in the HashMap.

Step 4: Traverse the original list and set the random pointers of cloned nodes based on mappings stored in the HashMap.

Step 5: Return the cloned head node obtained from the HashMap.

`import java.util.HashMap;class Node {    int val;    Node next, random;       public Node(int val) {        this.val = val;        this.next = null;        this.random = null;    }}public class CloneLinkedList {    public Node copyRandomList(Node head) {        if (head == null) return null;               // Step 1: Create a mapping between original and cloned nodes        HashMap<Node, Node> map = new HashMap<>();        Node curr = head;        while (curr != null) {            map.put(curr, new Node(curr.val));            curr = curr.next;        }          // Step 2: Set next and random pointers using the mapping        curr = head;        while (curr != null) {            map.get(curr).next = map.get(curr.next);            map.get(curr).random = map.get(curr.random);            curr = curr.next;        }             return map.get(head);    }       public static void main(String[] args) {        // Create the original linked list        Node one = new Node(1);        Node two = new Node(2);        Node three = new Node(3);        Node four = new Node(4);        Node five = new Node(5);        one.next = two;        one.random = three;        two.next = three;        two.random = four;        three.next = four;        three.random = five;        four.next = five;        four.random = three;        five.random = one;               // Call the copyRandomList() method        CloneLinkedList solution = new CloneLinkedList();        Node clonedHead = solution.copyRandomList(one);             // Print the original list        Node current = one;        System.out.print("Original Linked List: ");        while (current != null) {            System.out.print(current.val + "(" + (current.random != null ? current.random.val : "null") + ") ");            current = current.next;        }        System.out.println();              // Print the cloned list        current = clonedHead;        System.out.print("Cloned Linked List: ");        while (current != null) {            System.out.print(current.val + "(" + (current.random != null ? current.random.val : "null") + ") ");            current = current.next;        }    }}`

Output:

`Original Linked List: 1(3) 2(4) 3(5) 4(3) 5(1)Cloned Linked List: 1(3) 2(4) 3(5) 4(3) 5(1)`

Complexity Analysis:

Time Complexity: O(n), where n is the number of nodes in the linked list.

Space Complexity: O(n) due to the usage of HashMap.

## Approach: Modifying Original List

### Algorithm

Step 1: Traverse the original linked list and create a duplicate of each node, inserting it next to its original node.

Step 2: Iterate through the list again and adjust the next pointers of the cloned nodes to maintain the original sequence.

Step 3: While traversing the list, set the random pointers of the cloned nodes based on the random pointers of the original nodes.

Step 4: Separate the combined list into original and cloned lists by updating the next pointers of the original nodes and cloned nodes.

Step 5: Return the head of the cloned list obtained after the separation.

`class Node {    int val;    Node next, random;     public Node(int val) {        this.val = val;        this.next = null;        this.random = null;    }}public class CloneLinkedList1 {    public Node copyRandomList(Node head) {        if (head == null) return null;           // Step 1: Create a copy of each node and insert it next to its original node        Node curr = head;        while (curr != null) {            Node copy = new Node(curr.val);            copy.next = curr.next;            curr.next = copy;            curr = copy.next;        }             // Step 2: Adjust random pointers of the cloned nodes        curr = head;        while (curr != null) {            if (curr.random != null) {                curr.next.random = curr.random.next;            }            curr = curr.next.next;        }               // Step 3: Split the combined list into original and cloned lists        Node clonedHead = head.next;        curr = head;        while (curr != null) {            Node clone = curr.next;            curr.next = clone.next;            if (clone.next != null) {                clone.next = clone.next.next;            }            curr = curr.next;        }        return clonedHead;    }    public static void main(String[] args) {        // Create the original linked list        Node one = new Node(1);        Node two = new Node(2);        Node three = new Node(3);        Node four = new Node(4);        Node five = new Node(5);        one.next = two;        one.random = three;        two.next = three;        two.random = four;        three.next = four;        three.random = five;        four.next = five;        four.random = three;        five.random = one;        // Call the copyRandomList() method        CloneLinkedList1 solution = new CloneLinkedList1();        Node clonedHead = solution.copyRandomList(one);        // Print the original list        Node current = one;        System.out.print("Original Linked List: ");        while (current != null) {            System.out.print(current.val + "(" + (current.random != null ? current.random.val : "null") + ") ");            current = current.next;        }        System.out.println();          // Print the cloned list        current = clonedHead;        System.out.print("Cloned Linked List: ");        while (current != null) {            System.out.print(current.val + "(" + (current.random != null ? current.random.val : "null") + ") ");            current = current.next;        }    }}`

Output:

`Original Linked List: 1(3) 2(4) 3(5) 4(3) 5(1)Cloned Linked List: 1(3) 2(4) 3(5) 4(3) 5(1)`

Complexity Analysis:

Time Complexity: O(n), where n is the number of nodes in the linked list.

Space Complexity: O(1) as no extra space is used.

## Clone a Linked List with next and Random Pointer without using Extra Space

Cloning a linked list with next and random pointers without using extra space employs iterative manipulation of the original list structure to create corresponding nodes in the cloned list. By traversing the list iteratively and updating pointers, this approach duplicates the list while preserving both sequential and random relationships.

## Approach: Iterative

### Algorithm

Step 1: Create a duplicate of each node by inserting it next to its original node, forming a combined list.

Step 2: Modify the next pointers of cloned nodes to maintain the original sequence, alternating between original and cloned nodes.

Step 3: Set the random pointers of cloned nodes based on the random pointers of the original nodes, ensuring correct relationships.

Step 4: Separate the combined list into original and cloned lists by updating the next pointers of the original nodes.

Step 5: Return the head of the cloned list, representing the start of the cloned list without any additional space usage.

`class Node {    int val;    Node next, random;    public Node(int val) {        this.val = val;        this.next = null;        this.random = null;    }}public class CloneLinkedList2 {    public Node copyRandomList(Node head) {        if (head == null) return null;        // Step 1: Create a copy of each node and insert it next to its original node        Node curr = head;        while (curr != null) {            Node copy = new Node(curr.val);            copy.next = curr.next;            curr.next = copy;            curr = copy.next;        }        // Step 2: Adjust random pointers of the cloned nodes        curr = head;        while (curr != null) {            if (curr.random != null) {                curr.next.random = curr.random.next;            }            curr = curr.next.next;        }        // Step 3: Split the combined list into original and cloned lists        curr = head;        Node clonedHead = head.next;        Node cloneCurr = clonedHead;        while (curr != null) {            curr.next = curr.next.next;            curr = curr.next;            if (cloneCurr.next != null) {                cloneCurr.next = cloneCurr.next.next;                cloneCurr = cloneCurr.next;            }        }        return clonedHead;    }    public static void main(String[] args) {        // Create the original linked list        Node one = new Node(1);        Node two = new Node(2);        Node three = new Node(3);        Node four = new Node(4);        Node five = new Node(5);        one.next = two;        one.random = three;        two.next = three;        two.random = four;        three.next = four;        three.random = five;        four.next = five;        four.random = three;        five.random = one;        // Call the copyRandomList() method        CloneLinkedList2 solution = new CloneLinkedList2();        Node clonedHead = solution.copyRandomList(one);        // Print the original list        Node current = one;        System.out.print("Original Linked List: ");        while (current != null) {            System.out.print(current.val + "(" + (current.random != null ? current.random.val : "null") + ") ");            current = current.next;        }        System.out.println();        // Print the cloned list        current = clonedHead;        System.out.print("Cloned Linked List: ");        while (current != null) {            System.out.print(current.val + "(" + (current.random != null ? current.random.val : "null") + ") ");            current = current.next;        }    }}`
`Original Linked List: 1(3) 2(4) 3(5) 4(3) 5(1)Cloned Linked List: 1(3) 2(4) 3(5) 4(3) 5(1)`