Copy List with Random Pointer

Medium#138old node → new

You get a linked list where every node has, besides next, a link called random to any node of the same list or to none. Make a full copy: new nodes with the same values, and every link of the copy goes to a new node, never to an old one. Our example: 3 → 8 → 5 → 1, random 3 → 5, 8 → 3, 5 → none, 1 → 1 (itself).

138 Copy List with Random PointerWalkthrough · 1×

Example: the list 3 → 8 → 5 → 1; the arcs are random links. The copy is drawn below, its nodes marked ′.

listcopynone3851
the original listnode and its copycopy, no links yetcopy with its links

An empty map: it will tell, for every old node, which new node is its copy

01/34
restart · back · play · step
Speed
1function copyRandomList(head):
2 copy = empty map // copy[none] = none
3 node = head
4 while node is not none:
5 copy[node] = new node(node.val)
6 node = node.next
7 node = head
8 while node is not none:
9 copy[node].next = copy[node.next]
10 copy[node].random = copy[node.random]
11 node = node.next
12 return copy[head]
state
node
–
copy
{}
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A random link may point forward, to a node whose copy does not exist yet. So the first pass only makes the copies, and the second pass links them, when every copy is there.
  2. The map from an old node to its copy is what makes each link one lookup: the copy of node.random is copy[node.random], with no search through the list.
  3. Every link of a copy is taken from the map, and the map holds only new nodes, so nothing in the copy can lead back into the old list.

Complexity

Time O(n): two passes over the list, each lookup in the map is O(1). Memory O(n): the map holds one entry per node, besides the copy itself.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.