How do you copy a Linked List with random pointers? (Deep Copy)

Difficulty: 7/10

linked list, deep copy, random pointer

Deep Copy with Random Pointers

A linked list with random pointers requires a deep copy in which every original node gets a new corresponding node and each new random pointer refers to the copied target rather than the original target. A HashMap provides the simplest and most explicit solution.

javascript

1
Time complexity: O(n).
2
Auxiliary space: O(n) for the mapping.
3
The map ensures every original node maps to exactly one copied node.
4
Random pointers may point forward, backward, or to the same node.
5
An O(1) auxiliary-space solution is possible by interleaving copied nodes with original nodes before separating the lists.

Scenario Questions

0-2 years experience

Follow-up Questions