Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Copy List with Random Pointer

Copy List with Random Pointer

Master this topic with zero to advance depth.

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list.

Visual Representation

Original: [7,null] -> [13,0] -> [11,4] -> [10,2] -> [1,0] Where [val, random_index] Approach: Interweaving 1. Interweave: 7 -> 7' -> 13 -> 13' -> ... 2. Assign random: 7'.random = 7.random.next 3. Separate: 7 -> 13 and 7' -> 13'
Medium

Examples

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Approach 1

Level I: Using HashMap

Intuition

Use a hash map to store the mapping between the original node and the new node. First pass: create all clone nodes and map them. Second pass: link next and random pointers using the map.

⏱ O(N)💾 O(N)

Detailed Dry Run

Map: {7: 7', 13: 13', ...}.

  1. 7'.next = Map[7.next] -> 13'.
  2. 7'.random = Map[7.random] -> null.
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);
}

⚠️ Common Pitfalls & Tips

O(N) space is required for the map. Ensure the Node structure (with val, next, random) is understood.

Visual Mapping

Original: [A] -> [B] -> [C] Map: {A: A', B: B', C: C'} Step 2: A'.next = Map[B], A'.random = Map[C]
Approach 2

Level II: Recursive DFS with Map

Intuition

Use recursion to traverse the list. For each node, create a clone if it doesn't exist, and store it in a map. Then recursively copy next and random pointers. This naturally handles cycles and arbitrary pointers.

⏱ O(N)💾 O(N)

Detailed Dry Run

copy(7) -> 7'.

  1. 7'.next = copy(13).
  2. 7'.random = copy(null). Recursion handles the rest via map memoization.
java
private Map<Node, Node> visited = new HashMap<>();
public Node copyRandomList(Node head) {
    if (head == null) return null;
    if (visited.containsKey(head)) return visited.get(head);
    Node node = new Node(head.val);
    visited.put(head, node);
    node.next = copyRandomList(head.next);
    node.random = copyRandomList(head.random);
    return node;
}

⚠️ Common Pitfalls & Tips

Recursive depth can be an issue for very large lists. Ensure the map is used to prevent infinite recursion on random pointers.

Approach 3

Level III: Optimal (Interweaving Nodes)

Intuition

Instead of a hash map, we can interweave the cloned nodes with the original nodes. Step 1: Create a clone and insert it after each original node. Step 2: Assign random pointers. Step 3: Separate the interweaved lists.

⏱ O(N)💾 O(1)

Detailed Dry Run

7 -> 13 to 7 -> 7' -> 13 -> 13'.

  1. 7'.random = 7.random.next.
  2. Original: 7->13, Copy: 7'->13'.
java
public Node copyRandomList(Node head) {
    if (head == null) return null;
    Node curr = head;
    while (curr != null) { Node next = curr.next; curr.next = new Node(curr.val); curr.next.next = next; curr = next; }
    curr = head;
    while (curr != null) { if (curr.random != null) curr.next.random = curr.random.next; curr = curr.next.next; }
    Node dummy = new Node(0), copyTail = dummy, original = head;
    while (original != null) {
        Node copy = original.next;
        original.next = copy.next;
        copyTail.next = copy;
        copyTail = copy;
        original = original.next;
    }
    return dummy.next;
}

⚠️ Common Pitfalls & Tips

Be extremely careful when separating the interweaved list; you must restore the original list as well.

← Previous QuestionReorder List
Next Question →Add Two Numbers