Sweaty Imposter

Copy List with Random Pointer

MediumLinked ListNeetCode 150MidOpen on LeetCodeUpdated

You're given the head of a linked list where each node has a value, a next pointer, and a random pointer that can point to any node in the list or to null. Return a deep copy: a new list of new nodes with the same values, where each copy's next and random pointers point to the matching copies. No pointer in the copy may point back into the original list.

Examples

head = [[5,null],[9,0],[2,1]] returns [[5,null],[9,0],[2,1]]

Each pair is [value, index of the random target]. The copy of 9 must point its random pointer at the copy of 5, and the copy of 2 at the copy of 9.

head = [[4,0]] returns [[4,0]]

The single node's random pointer points to itself, so the copy must point to itself too.

head = [] returns []

An empty list copies to an empty list.

Constraints

  • 0 <= n <= 1000
  • -10^4 <= Node.val <= 10^4
  • Node.random is null or points to a node in the list.

Hints

Hint 1

Copying next pointers in one pass is easy. Why does the random pointer get in the way?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

The difficulty is that a random pointer can point to a node whose copy does not exist yet. Solve it in two passes with a hash map from each original node to its copy. The first pass creates every copy with just its value. The second pass sets copy.next = map[node.next] and copy.random = map[node.random], with null mapping to null. O(n) time and O(n) space. Interleaving each copy right after its original removes the map and brings the space to O(1), at the cost of trickier pointer work.

Time

O(n)

Space

O(n)

Pitfall

Copying the random pointer directly, so the new node points into the original list. The result looks right when printed but is a shallow copy.

Solutions

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> copies = new HashMap<>();
        for (Node cur = head; cur != null; cur = cur.next) {
            copies.put(cur, new Node(cur.val));
        }
        for (Node cur = head; cur != null; cur = cur.next) {
            Node copy = copies.get(cur);
            copy.next = copies.get(cur.next);
            copy.random = copies.get(cur.random);
        }
        return copies.get(head);
    }
}
Drill This