How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Clone list with random pointers | Meta Coding Question

Quick Overview

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.

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.

Input: ([[3, None], [3, 0], [3, None]],)

Expected Output: [[3, None], [3, 0], [3, None]]

Explanation: Duplicate values (all 3) with a mix of null and non-null randoms. Identity-keyed cloning must not be confused by equal values; only the middle node has a random link.

Input: ([],)

Expected Output: []

Explanation: Empty list corner case — returns an empty result, exercising the head-is-null early exit.

Input: ([[5, 0]],)

Expected Output: [[5, 0]]

Explanation: Single node whose random points to itself (index 0). The clone's random must point to the clone itself, not the original, and must serialize back to index 0.

Input: ([[1, None]],)

Expected Output: [[1, None]]

Explanation: Single node with a null random — degenerates to copying an ordinary one-element list.

Input: ([[-7, 2], [9, 0], [0, 1], [4, None]],)

Expected Output: [[-7, 2], [9, 0], [0, 1], [4, None]]

Explanation: Negative and zero values with random links forming a small cycle among nodes 0->2->1->0, plus a tail with null random. Confirms cycles in the random graph are handled without infinite loops.

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.

Last updated: Jun 26, 2026

Loading coding console...