Pattern Recognition Drill

#137 — Copy List with Random Pointer

Medium Linked Lists

The Problem

Deep copy a linked list where each node has a next pointer and a random pointer to any node.

What approach would you use?

Think about it before scrolling down.

Key Signals

Hash Map

First pass: map each original → clone. Second pass: set next and random using the map. O(n).

Alt: Pointer Walk

Interleave clones: A→A'→B→B'→... Set random pointers, then separate. O(1) space.

Common Trap

Don't forget to handle None random pointers. The hash map approach is cleaner than interleaving.

← #136