Each node of this singly linked list has a value, a next pointer, and a second pointer jump that may point to any node of the same list (earlier, later, itself) or be None. Nodes are instances of the provided Node class.
Write copy_list(head) that returns the head of a brand-new list with the same shape:
- it has the same number of nodes with the same values, in the same order;
- if the
jumpof the original's i-th node points to its j-th node, thejumpof the copy's i-th node points to the copy's j-th node (andNonestaysNone); - no node of the copy is an original node, and no pointer of the copy leads back into the original list.
The original list must look exactly as it did before when you return (you may change it temporarily). An empty list is None.
a, b, c = Node(1), Node(2), Node(3)
a.next, b.next = b, c
a.jump, b.jump, c.jump = c, a, c
new = copy_list(a)
new is a # False
[new.val, new.next.val, new.next.next.val] # [1, 2, 3]
new.jump is new.next.next # True (the copy's own third node)
new.next.jump is new # True
new.next.next.jump is new.next.next # True
copy_list(None) # None
Constraints: up to 200,000 nodes; values are any ints and may repeat, so you can't find a node by its value. Lists this long rule out recursion. Aim for O(n) time.
Show hint
The hard part is knowing, for an original node, which new node stands for it. Record that correspondence as you create the new nodes, then wire up the pointers in a second pass.