Medium
Quiz
#138 Copy List with Random Pointer
APPROACH
A linked list of length n is given; each node holds an extra random pointer that may point to any node in the list or to null.
Produce a deep copy of the list — a brand-new list of n nodes where each new node's value, next pointer, and random pointer mirror those of the corresponding original node. No pointer in the copy may reference a node from the original list.
Return the head of the copied list.
The list is encoded as n pairs [val, random_index] where:
- val: the node's integer value.
- random_index: the 0-based index of the node targeted by random, or null if none.
Your code receives only the head of the original list.
Example 1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Example 2:
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Example 3:
Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
1 of 4
1:00
What is the optimal approach for this problem?