Description
Clone a linked list with next and random pointers. random can reference any node or be null. The result must share no nodes with the original. Examples use [value, random_index] pairs; null means no random target.
Solution
def copy_random_list(head):
copies = {None: None}
current = head
while current:
copies[current] = Node(current.val)
current = current.next
current = head
while current:
copies[current].next = copies[current.next]
copies[current].random = copies[current.random]
current = current.next
return copies[head]Examples
Example 1
- Input
[[[7,null],[13,0],[11,1]]]- Output
[[7,null],[13,0],[11,1]]
Preserve pointer indices in newly allocated nodes.
Example 2
- Input
[[[1,0]]]- Output
[[1,0]]
The clone's random pointer refers to itself.
Example 3
- Input
[[]]- Output
[]
An empty input has an empty clone.
Approach
Create every clone first and map original nodes to clones. Then connect next and random pointers through that map.
Time & space
O(n) time and O(n) auxiliary space for n nodes.