DSA interview question

Clone a Linked List with Next and Random Pointers

Hard · Data structures · Topics: linkedlist, hash map

The problem

A workflow tool stores each process as a linked list of steps. Besides next, every step has a random pointer to any step in the same process (for example, "if this fails, go back to step X"), or nullptr. Users want to duplicate a process, which requires a deep copy: brand-new nodes whose next and random pointers point to the new nodes in the same pattern. The obvious solution maps each original to its copy in a hash map. The classic O(1)-extra-space trick weaves each copy right after its original, so a copy's random target is always original->random->next.

Example: [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]] (value, index of the random target) → a new list with exactly the same structure.

Function signature

Node* copyRandomList(Node* head);  // returns the head of a deep copy; the original must be left unchanged

Test cases

Input `[value, random index]`	Output (the clone)	Explanation
`[[7,null],[13,0],[11,4],[10,2],[1,0]]`	`[[7,null],[13,0],[11,4],[10,2],[1,0]]`	Same shape, all new nodes
`[[1,1],[2,1]]`	`[[1,1],[2,1]]`	Node 1's random points to itself
`[[3,null],[3,0],[3,null]]`	`[[3,null],[3,0],[3,null]]`	Equal values, so identity matters
`[[5,0]]`	`[[5,0]]`	A self-loop through random
`[]`	`[]`

(Confirm: no clone pointer may point into the original list; the original's next and random pointers must be restored.)

How interviewers phrase it

"Copy list with random pointer" (LeetCode 138).
"Clone a linked list with next and random pointers in O(1) extra space" (GeeksforGeeks).

Clarifying questions to ask

Can random be null or point to the node itself? (Both are allowed.)
Must the original list be left unchanged afterwards? (Yes.)
Is O(n) extra memory acceptable, or is O(1) expected?

Follow-ups to expect

"What's the simple approach?"
"How do you avoid the map?"
"Why three separate passes?"
"How do you restore the original?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview