Clone a Linked List with Next and Random Pointer
Problem link: https://www.geeksforgeeks.org/problems/clone-a-linked-list-with-next-and-random-pointer/1
Problem Statement
You are given a linked list where each node has two pointers:
next: points to the next noderandom: points to any node in the list (ornull)
Create a deep copy of the list. The cloned list must have the same structure (both next and random), but must contain new nodes.
Input
- A linked list head where each node has
nextandrandompointers. randommay benullor point to any node (including itself).
Output
- Return the head of the deep-copied linked list.
Example
List: 1 -> 3 -> 5 -> 9
random(1) -> 5
random(3) -> 1
random(5) -> 3
random(9) -> null
Explanation
We must create new nodes (1', 3', 5', 9') such that:
- Next structure remains same
- Random pointers point to cloned nodes, not original ones
Final: 1' -> 3' -> 5' -> 9' random(1') -> 5' random(3') -> 1' random(5') -> 3' random(9') -> null
Brute Force
Intuition
The challenge is that random pointers can point anywhere. So while cloning a node, we may not yet know the clone of the random target. To solve this, we separate node creation and pointer linking using a HashMap.
We first create all nodes and store mapping from original → clone. Then we connect next and random pointers using that mapping.
Approach
- Traverse list and create clone node for each original node
- Store mapping original → clone
- Traverse again:
- clone.next = map(original.next)
- clone.random = map(original.random)
- Return cloned head
Code (Java)
import java.util.HashMap;
import java.util.Map;
public class Solution {
static class Node {
int data;
Node next, random;
Node(int d) { data = d; }
}
public static Node copyRandomList(Node head) {
if (head == null) return null;
Map<Node, Node> map = new HashMap<>();
Node cur = head;
while (cur != null) {
map.put(cur, new Node(cur.data));
cur = cur.next;
}
cur = head;
while (cur != null) {
Node clone = map.get(cur);
clone.next = map.get(cur.next);
clone.random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}
Complexity Analysis
- Time: Two passes → O(N)
- Space: HashMap → O(N)
Optimal Solution
Intuition
We avoid extra space by inserting cloned nodes directly next to original nodes. This creates an implicit mapping using structure itself.
If X → X', then X.random.next gives X'.random target.
Approach
- Insert clone after each node
- Assign random using original.random.next
- Separate lists
Code (Java)
public class Solution {
static class Node {
int data;
Node next, random;
Node(int d) { data = d; }
}
public static Node copyRandomList(Node head) {
if (head == null) return null;
Node cur = head;
while (cur != null) {
Node clone = new Node(cur.data);
clone.next = cur.next;
cur.next = clone;
cur = clone.next;
}
cur = head;
while (cur != null) {
if (cur.random != null) {
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}
Node dummy = new Node(0);
Node tail = dummy;
cur = head;
while (cur != null) {
Node clone = cur.next;
Node next = clone.next;
tail.next = clone;
tail = clone;
cur.next = next;
cur = next;
}
return dummy.next;
}
}
Complexity Analysis
- Time: Three passes → O(N)
- Space: O(1)
Key insight: structure itself acts as mapping
Quick Revision (Brute Force)
- Use HashMap original → clone
- Two pass solution
- Simple but uses extra space
Quick Revision (Optimal)
- Interleave nodes
- Use original.random.next
- Separate lists
- No extra space