LeetCode 206 · Easy · Linked List

Reverse Linked List

Given the head of a singly linked list, reverse the list in place and return the new head.

O(n)time
O(1)space
3 pointersprev · curr · nxt

list values in order · 0–10 integers, −99 to 99 · empty or [] for an empty list

Linked list box = value · slot = next pointer · ∅ = null

public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nxt = curr.next; // save the rest curr.next = prev; // flip the arrow prev = curr; curr = nxt; } return prev;}
prev
—
curr
—
nxt
—
reversed
—
rest
—

Why it works

  1. Brute force copies: push every value on a stack (or into an array) and rebuild the list. O(n) time but O(n) extra space. Rewiring the existing arrows needs O(1).
  2. The invariant: prev heads the already-reversed part and curr heads the untouched rest. Each pass moves one node from the rest to the front of the reversed part.
  3. Order matters. curr.next = prev destroys the only link to the rest, so nxt must be saved first. Swap lines 5 and 6 and the list is cut off after one node.
  4. Return prev, not curr: the loop ends when curr is null, and prev then holds the old tail, the new head. Empty and one-node lists need no special case.
  5. One pass, three pointers: O(n) time, O(1) space.
  6. Recursive version: ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; (base case: head == null || head.next == null returns head). Same O(n) time, but O(n) call stack: a very long list can throw StackOverflowError. Reversing only part of a list (LeetCode 92) reuses the same three-pointer loop.