Reverse Linked List

Easy#206reverse

You get the head of a singly linked list. Turn the list around so that every link points the other way, and return the new head. Our example: 4 → 7 → 2 → 9 — the answer is 9 → 2 → 7 → 4.

206 Reverse Linked ListWalkthrough · 1×

Example: reverse 4 → 7 → 2 → 9 in place.

nonenone4729prevhead
not reached yetcurnext, savedreversed, starts at prev

prev = none: nothing is reversed yet

01/24
restart · back · play · step
Speed
1function reverseList(head):
2 prev = none
3 cur = head
4 while cur is not none:
5 next = cur.next
6 cur.next = prev
7 prev = cur
8 cur = next
9 return prev
state
prev
none
cur
–
next
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. next is saved before cur.next is overwritten, so the rest of the list is never lost: it is the only way to it.
  2. Everything left of cur is already reversed and starts at prev; each step moves one node from the old list to the front of the reversed one.
  3. The old head ends up last, pointing to none, and head still points at it. The new head is the last node prev reached.

Complexity

Time O(n): one pass, each node is turned around once. Memory O(1): three pointers, no new nodes.

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.