DSAMotivator

Reverse Linked List

Easy·🔗 Linked List·Open on LeetCode ↗

Turn every next-pointer in a singly linked list around, so the last node becomes the head and the first becomes the tail.

head = [3, 1, 4, 5]step 1/10
3145

Arrows all point right. Every one of them has to end up pointing left.

1def reverse_list(head):
2    prev = None
3    curr = head
4    while curr:
5        nxt = curr.next
6        curr.next = prev
7        prev = curr
8        curr = nxt
9    return prev
Read the 10 steps as text
  1. 1Arrows all point right. Every one of them has to end up pointing left.
  2. 2At 3. Save the forward link to 1 before overwriting it.
  3. 3Point 3 at prev, which is null. The old head is now the tail.
  4. 4At 1. Save the forward link to 4 before overwriting it.
  5. 5Point 1 back at 3. That arrow is now reversed for good.
  6. 6At 4. Save the forward link to 5 before overwriting it.
  7. 7Point 4 back at 1. That arrow is now reversed for good.
  8. 8At 5. Nothing after it, so next is null — this is the last node.
  9. 9Point 5 back at 4. That arrow is now reversed for good.
  10. 10curr ran off the end, so prev is the new head. The list now reads 5 → 4 → 1 → 3.

The idea

A singly linked list can only be walked forwards, and reversing it means every node must end up pointing at the node that currently points at *it*. The catch is that once you overwrite a node's next-pointer, the rest of the list is unreachable — you've sawn off the branch you were standing on.

So the whole problem is one of ordering: save the forward link before you destroy it. That's what the temporary `nxt` is for, and it's the only reason the loop needs three variables instead of two.

After that it's a walk. At each node you know where you came from (`prev`), where you are (`curr`), and where you were going (`nxt`). Point curr backwards, then shuffle all three one step to the right. When curr falls off the end, prev is standing on the last real node — which is the new head.

`prev` starting at null isn't an edge case, it's the answer to 'what should the old head point to?'. The old head becomes the tail, and a tail points at null. Initialising prev to null makes the first iteration do that for free.

The approach

  1. 1Set prev to null and curr to the head.
  2. 2While curr isn't null: save curr.next into nxt.
  3. 3Point curr.next at prev — this is the actual reversal.
  4. 4Move prev to curr and curr to nxt.
  5. 5When the loop ends, curr is null and prev is the new head. Return prev.

Complexity

Time
O(n)
Space
O(1)

One pass, and the only extra memory is three pointers regardless of list length. The recursive version is also O(n) time but O(n) space for the call stack, which is the trade worth naming out loud.

Code

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

What goes wrong

  • •Writing `curr.next = prev` before saving `curr.next`. The remainder of the list is now orphaned and the loop can't advance — this is the mistake, and it's why the temporary exists.
  • •Returning `head` at the end. head is still the original first node, which is now the tail, so you return a one-element list. The answer is `prev`.
  • •Initialising prev to the head instead of null, which leaves a cycle between the first two nodes and hangs anything that later walks the list.
  • •Being unable to say why the loop condition is `curr` and not `curr.next`. Stopping at `curr.next` leaves the final node unreversed — worth stating that you considered it.