Algorithm-Day33-Copy-List-with-Random-Pointer-lc-138

Posted on In , Views:

🧩 Problem Description

A linked list is given where each node has two pointers:

  • next: points to the next node
  • random: can point to any node in the list or be null

Return a deep copy of the list.

Each node in the new list must have the same value and the same random structure — but must be a new node, not shared.

💬 Example

1
2
3
4
5
6
7
Input:
Node1: val = 7, next = Node2, random = null
Node2: val = 13, next = Node3, random = Node1
...

Output:
Deep copy of the above structure

💡 Approach 1: HashMap Mapping (Straightforward)

✨ Idea

  • Traverse original list, and use a HashMap<OldNode, NewNode> to:
    • Store the mapping between original nodes and copied ones
    • After building the copy, set the next and random pointers

🔢 Java Code (Using HashMap)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        Map<Node, Node> map = new HashMap<>();

        // Step 1: Create all nodes and store mapping
        Node curr = head;
        while (curr != null) {
            map.put(curr, new Node(curr.val));
            curr = curr.next;
        }

        // Step 2: Assign next and random pointers
        curr = head;
        while (curr != null) {
            Node copy = map.get(curr);
            copy.next = map.get(curr.next);
            copy.random = map.get(curr.random);
            curr = curr.next;
        }

        return map.get(head);
    }
}
  • Time Complexity: O(n)
  • Space Complexity: O(n) — due to the map

💡 Approach 2: Interleaving Nodes (O(1) Extra Space)

✨ Key Idea

  1. Clone each node and insert it right after the original:
    • A → A' → B → B' → ...
  2. Assign random pointers:
    A'.random = A.random.next
  3. Detach the new list from the original

🔢 Java Code (No Extra Space)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        // Step 1: Clone and insert nodes
        Node curr = head;
        while (curr != null) {
            Node clone = new Node(curr.val);
            clone.next = curr.next;
            curr.next = clone;
            curr = clone.next;
        }

        // Step 2: Assign random pointers
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }

        // Step 3: Detach the clone list
        Node dummy = new Node(0);
        Node copyCurr = dummy;
        curr = head;

        while (curr != null) {
            Node clone = curr.next;
            copyCurr.next = clone;
            copyCurr = clone;

            curr.next = clone.next;  // Restore original list
            curr = curr.next;
        }

        return dummy.next;
    }
}

  • Time Complexity: O(n)
  • Space Complexity: O(1)

✍️ Summary

  • Understand how to maintain relationships with .random using either:
    • Hash map mapping (O(n) space)
    • Interleaved list strategy (O(1) space)
  • This is a deep copy problem with pointer manipulation — commonly tested in interviews

Practice building clones of linked structures while preserving complex references. This is a great test of both logic and implementation skill.