Clone list with random pointers
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
You are given the `head` of a singly linked list where each node has two pointers: `next` and `random`. The `random` pointer may be `null` or point to **any** node in the list (including itself). Construct a **deep copy** of the list and return the head of the copy. The copied list must consist of brand-new nodes, and each copied node's `next`/`random` must point to the corresponding **copied** node, never to a node in the original list.
1. **Core deep copy.** Build a deep copy in O(n) time. Walk through the original once and reproduce both the `next` chain and the arbitrary `random` links among the new nodes.
2. **Hash-map approach.** Explain the straightforward solution that uses a map from each original node to its clone, then a second pass to wire up `next` and `random`. State its O(n) time and O(n) auxiliary space.
3. **In-place weaving approach.** Explain the interleaving (weave/unweave) technique that achieves **O(1) auxiliary space** beyond the new nodes: clone each node and splice it directly after its original (`A -> A' -> B -> B' -> ...`), assign each clone's `random` from `orig.random.next`, then unweave the two lists to restore the original and extract the copy.
4. **Handling cycles in random pointers.** Discuss why the algorithm stays correct when `random` pointers form cycles or point backward (you copy *links*, not by traversal order, so cycles never cause infinite loops or re-cloning).
5. **Verifying correctness.** Describe how you verify structural equality of the copy against the original: same length, equal node values in order, the `random` of each copied node maps to the correct relative position, and that **no copied pointer escapes into the original list** (deep-copy isolation).
6. **Corner cases.** Make sure the solution handles an empty list, a single-node list (including a node whose `random` points to itself), and a list where every `random` is `null`.
Quick Answer: Meta software-engineer technical-screen coding question: deep-copy a singly linked list whose nodes carry an arbitrary random pointer (which may be null, point backward, or form cycles). It tests both the O(n)-space hash-map solution and the O(1)-auxiliary-space in-place weaving technique, plus reasoning about pointer integrity, cycle safety, and verifying the copy is structurally equal to and isolated from the original.
You are given a singly linked list where each node has a `next` pointer and a `random` pointer. The `random` pointer may be null or point to **any** node in the list (including the node itself). Build a **deep copy** of the list: brand-new nodes whose `next`/`random` only ever reference the copied nodes, never the originals.
**Input / output encoding.** Because raw node references can't be passed across a function boundary, the list is represented as an array of `[val, random_index]` pairs in `next`-order. `random_index` is the 0-based index of the node that this node's `random` points to, or `null` (`None` in Python) if `random` is null. Your function receives this encoding for the original list and must return the **same encoding for the deep copy**. A correct deep copy serializes to exactly the same array as the input.
Example: input `[[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]` describes 5 nodes; node 1 (val 13) has `random` -> node 0, node 2 (val 11) has `random` -> node 4, etc. The correct output is the identical array, proving the copy preserves every `next` and `random` link.
**What to demonstrate:**
1. **Hash-map approach** — map each original node to its clone, then a second pass wires `next` and `random`. O(n) time, O(n) space.
2. **In-place weaving approach** — interleave each clone after its original (`A -> A' -> B -> B' -> ...`), set each clone's `random` from `orig.random.next`, then unweave. O(n) time, O(1) auxiliary space.
3. **Cycles in `random`** are harmless because neither method *traverses* `random` edges — links are copied by lookup, so a node is never re-cloned and there is no infinite loop.
4. Handle the corner cases: empty list, single node (including `random` pointing to itself), and a list where every `random` is null.
Constraints
- 0 <= number of nodes <= 1000
- -10000 <= node value <= 10000
- random_index is either null (no random pointer) or a valid 0-based index into the list
- random pointers may point backward, forward, to the same node (self), or form cycles
- The returned copy must be fully isolated: no copied node's next/random may reference an original node
Examples
Input: ([[7, None], [13, 0], [11, 4], [10, 2], [1, 0]],)
Expected Output: [[7, None], [13, 0], [11, 4], [10, 2], [1, 0]]
Explanation: Canonical LeetCode-138 example: 5 nodes with assorted backward/forward random links. The deep copy must serialize to the identical array, proving every next and random link was reproduced among the new nodes.
Input: ([[1, 1], [2, 1]],)
Expected Output: [[1, 1], [2, 1]]
Explanation: Two nodes where both random pointers target node 1. Tests that multiple originals can share a random target and the copy preserves that aliasing among clones.
Hints
- First pass: create a clone for every original node and store the mapping original-node -> clone in a hash map. Second pass: for each original node, set clone.next = map[orig.next] and clone.random = map[orig.random], letting null map to null.
- Never *follow* a random pointer while constructing the copy — only look it up in the map. That is exactly why random cycles or self-references can never cause an infinite loop or a double-clone.
- For O(1) auxiliary space, weave each clone directly after its original (A -> A' -> B -> B' -> ...). Then clone.random is simply orig.random.next, and a final unweaving pass restores the original list and extracts the copy.
- Watch the corner cases: an empty list returns an empty result, and a single node whose random points to itself must serialize with random_index 0.