A linked list where each node has an additional random pointer which can point to any node in the list or null. Construct a deep copy of the list.
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Explanation: Each pair is [val, random_index].
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Two-pass approach using a HashMap mapping original nodes to their copies.
- Pass 1: Create copy of each node, store in map (original → copy)
- Pass 2: Set next and random pointers using the map
public Node copyRandomList(Node head) {
if (head == null) return null;
Map<Node,Node> map = new HashMap<>();
Node curr = head;
while (curr != null) { map.put(curr, new Node(curr.val)); curr = curr.next; }
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);
}
Complexity Analysis:
Time complexity: O(n)
Space complexity: O(n) — HashMap for node mapping