Copy List with Random Pointer

Share

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.

Example 1
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].
Example 2
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Solution Approach

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
Java
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