LinkedListProblem 30 of 36
Clone a linked list with next and random pointer
Clone a Linked List with Next and Random Pointer
Problem Statement
Given a linked list where each node has two pointers: next pointing to the next node and random pointing to any node in the list (or null). Create a deep copy of the list where the cloned list has the same structure.
Example
Input:
Node 1 -> Node 2 -> Node 3 -> Node 4 -> Node 5
Random pointers: 1->3, 2->1, 3->5, 4->3, 5->2
Output: A new list with same structure where:
- All nodes are newly created
- next pointers follow same pattern
- random pointers point to corresponding cloned nodes
Brute Force Approach (Using HashMap)
Intuition
Use a HashMap to store the mapping between original nodes and their clones. In the first pass, create all clone nodes and store the mapping. In the second pass, set up the next and random pointers using the mapping.
Algorithm
- First pass: Create clone nodes and store original->clone mapping in HashMap
- Second pass: For each original node, set its clone's next and random pointers using the HashMap
- Return the clone of the head
Code
java
import java.util.HashMap;
import java.util.Map;
class Node {
int data;
Node next;
Node random;
Node(int data) {
this.data = data;
this.next = null;
this.random = null;
}
}
public class CloneListHashMap {
public static Node cloneListHashMap(Node head) {
if (head == null) return null;
Map<Node, Node> nodeMap = new HashMap<>();
// First pass: Create all clone nodes
Node curr = head;
while (curr != null) {
nodeMap.put(curr, new Node(curr.data));
curr = curr.next;
}
// Second pass: Set up next and random pointers
curr = head;
while (curr != null) {
Node clone = nodeMap.get(curr);
clone.next = nodeMap.get(curr.next);
clone.random = nodeMap.get(curr.random);
curr = curr.next;
}
return nodeMap.get(head);
}
public static void printList(Node head) {
Node curr = head;
while (curr != null) {
String randomVal = (curr.random != null) ? String.valueOf(curr.random.data) : "NULL";
System.out.println("Node(" + curr.data + ") random->" + randomVal);
curr = curr.next;
}
}
}Complexity Analysis
- Time Complexity: O(n) - Two passes through the list
- Space Complexity: O(n) - HashMap to store node mappings
Optimal Approach (Interweaving Nodes)
Intuition
Instead of using extra space for mapping, we interweave clone nodes with original nodes. Insert each clone right after its original, use this structure to set random pointers, then separate the two lists.
Algorithm
- Step 1: Insert clone nodes between original nodes
- Original: A -> B -> C
- After: A -> A' -> B -> B' -> C -> C'
- Step 2: Set random pointers for clones
- clone.random = original.random.next (if exists)
- Step 3: Separate the two lists
- Extract clones while restoring original list
Code
java
class Node {
int data;
Node next;
Node random;
Node(int data) {
this.data = data;
this.next = null;
this.random = null;
}
}
public class CloneListOptimal {
public static Node cloneListOptimal(Node head) {
if (head == null) return null;
// Step 1: Insert clone nodes between original nodes
Node curr = head;
while (curr != null) {
Node clone = new Node(curr.data);
clone.next = curr.next;
curr.next = clone;
curr = clone.next;
}
// Step 2: Set random pointers for clones
curr = head;
while (curr != null) {
if (curr.random != null) {
curr.next.random = curr.random.next;
}
curr = curr.next.next;
}
// Step 3: Separate the two lists
Node cloneHead = head.next;
curr = head;
Node cloneCurr = cloneHead;
while (curr != null) {
curr.next = curr.next.next;
if (cloneCurr.next != null) {
cloneCurr.next = cloneCurr.next.next;
}
curr = curr.next;
cloneCurr = cloneCurr.next;
}
return cloneHead;
}
public static void printList(Node head) {
Node curr = head;
while (curr != null) {
String randomVal = (curr.random != null) ? String.valueOf(curr.random.data) : "NULL";
System.out.println("Node(" + curr.data + ") random->" + randomVal);
curr = curr.next;
}
}
public static void main(String[] args) {
// Create: 1 -> 2 -> 3 -> 4 -> 5
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
// Set random pointers
head.random = head.next.next;
head.next.random = head;
head.next.next.random = head.next.next.next.next;
head.next.next.next.random = head.next.next;
head.next.next.next.next.random = head.next;
System.out.println("Original list:");
printList(head);
Node cloned = cloneListOptimal(head);
System.out.println("\nCloned list:");
printList(cloned);
System.out.println("\nOriginal list (after cloning):");
printList(head);
}
}Complexity Analysis
- Time Complexity: O(n) - Three passes through the list
- Space Complexity: O(1) - No extra data structures (cloned nodes don't count)
Visual Representation
Original: A -----> B -----> C -----> D
| | | |
+---random---> +--random->
After Step 1: A -> A' -> B -> B' -> C -> C' -> D -> D'
After Step 2: A -> A' -> B -> B' -> C -> C' -> D -> D'
| | | | | | | |
(random pointers set for clones)
After Step 3: Original: A -> B -> C -> D
Clone: A'-> B'-> C'-> D'
Key Takeaways
- Deep Copy Challenge: The random pointer makes cloning non-trivial
- HashMap Approach: Simple and intuitive but uses O(n) extra space
- Interweaving Technique: Clever use of structure to avoid extra space
- Three-Step Process: Insert -> Connect Random -> Separate
- Restore Original: The optimal approach must restore the original list
- Classic Interview Problem: LeetCode #138 - Copy List with Random Pointer
- Space-Time Trade-off: O(1) space requires careful pointer manipulation