Reversing a linked list

Walk the list once and turn each node's arrow to point backwards. Three pointers do it: curr is the node being turned, prev is where its arrow should now point, and next remembers the rest of the list before the arrow is changed.

O(n)in placeone pass

Reverse the list so every arrow points the other way. Press play or step forward to start.

step 0 / 22

1function reverse(head) {2  let prev = null, curr = head;3  while (curr !== null) {4    const next = curr.next;5    curr.next = prev;6    prev = curr;7    curr = next;8  }9  return prev;10}

Keys: Space play or pause, ← → step. The URL always points at the frame you are on.

What it costs

Case	Time	When
best	n	every node is visited once
average	n	one arrow turned per node
worst	n	the same for every input
space	1	just prev, curr and next

Where it breaks

Turning the arrow before saving next. Once curr.next = prev runs, the only way to the rest of the list is gone. Save next first, every time.
Returning the old head. When the loop ends, curr is null and the old head is now the last node. The new head is prev.
Recursion instead. A recursive reverse reads neatly, but it keeps one waiting call per node, so long lists can overflow the stack. This loop needs three pointers whatever the length.