progress

~/problems / Linked lists / Linked lists

Copy List with Random Pointer

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium ~30 min

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 jump of the original's i-th node points to its j-th node, the jump of the copy's i-th node points to the copy's j-th node (and None stays None);
  • 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
A list 1, 2, 3 with next arrows and jump arrows from 1 to 3, from 2 back to 1, and from 3 to itself; the copy has the same shape using only its own nodes

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.

⭐ Bonus: a speed test with 200,000 nodes earns a star in 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.

Topic: Linked lists. Dummy heads, pointer rewiring, fast/slow pointers.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc