Questions
10 of 16
How do you copy a Linked List with random pointers? (Deep Copy)
Difficulty: 4/10
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.
Follow-up Questions
- How can this be solved with O(1) extra space?
- What happens if a random pointer is null?
- Why is a shallow copy incorrect?