138. Copy List with Random Pointer

Each node of a linked list has a next pointer and a random pointer to any node or null. Return a deep copy of the list. Input encodes each node as [val, random index].

Insert each copy right after its original (A → A' → B → B'). Then A'.random = A.random.next. Finally unzip the two lists.

1function copyRandomList(head: Node | null): Node | null {
2  for (let n = head; n; n = n.next.next) n.next = new Node(n.val, n.next);
3  for (let n = head; n; n = n.next.next) n.next.random = n.random ? n.random.next : null;
4  const dummy = new Node(0);
5  for (let n = head, tail = dummy; n; n = n.next) {
6    tail = tail.next = n.next;
7    n.next = n.next.next;
8  }
9  return dummy.next;
10}

list

→

→ ∅

random pointers

#0 → null

#0' → null

#1 → #0

#2 → #4

#3 → #2

#4 → #0

Insert #0' right after #0.

1 / 0

Space: play/pause · ←/→: step