#109

Reverse Linked List

easy

linked-listrecursion

Given the head of a singly linked list, reverse the list and return the head of the reversed list.

Your function receives and returns a ListNode chain; the examples below show each list in array notation for readability — [1, 2, 3, 4, 5] is the chain 1 -> 2 -> 3 -> 4 -> 5, which reverses to 5 -> 4 -> 3 -> 2 -> 1.

Example

Input: head = [1,2,3,4,5]12345null

Output: [5,4,3,2,1]54321null

1->2->3->4->5 reverses to 5->4->3->2->1.

Constraints

The number of nodes in the list is in the range [0, 5000].
-5000 <= Node.val <= 5000

Intuition

The most direct approach sidesteps pointer surgery entirely: walk the list collecting the values into an array, then build a brand-new list from that array read back-to-front.

function reverseList(head) {
  // Walk once, copying every value into an array.
  const values = [];
  for (let node = head; node; node = node.next) {
    values.push(node.val);
  }
  // Build a fresh list from the values, last value first.
  let newHead = null;
  for (const val of values) {
    newHead = new ListNode(val, newHead); // prepend → reverses order
  }
  return newHead;
}

Brute force — collect values, rebuild reversed: O(n) time, O(n) extra space.

This works, but it allocates a whole second list plus the values array — O(n) extra space for a problem that's really just relinking nodes we already have. Can we do better?

The key observation: reversing a list means flipping the direction of every next pointer. Node by node, 1 -> 2 -> 3 becomes 1 <- 2 <- 3. We don't need new nodes at all — we can rewire the existing ones in a single pass.

The catch is that the moment we set curr.next = prev, we've destroyed the link to the rest of the list. So before flipping, stash curr.next in a temporary next. Carry three pointers — prev (the reversed part so far, starting at null), curr (the node being flipped), and the saved next — and slide them forward together.

Walking it through on 1 -> 2 -> 3:

reversing 1 -> 2 -> 3 in place

curr↓

prev↓

null

save next = 2; curr.next = prev

Start: prev = null, curr = node 1. Stash node 1's next (node 2), then flip node 1's link to null.

prev↓

curr↓

null

save next = 3; curr.next = prev

Slide forward: prev = node 1, curr = node 2. Node 1 now points at null. Flip node 2's link back to node 1.

prev↓

curr↓

null

save next = null; curr.next = prev

prev = node 2, curr = node 3. Node 2 points back at node 1. Flip node 3's link back to node 2.

prev↓

curr↓

null

curr = null → stop

curr fell off the end. Every link now faces backward: 3 -> 2 -> 1 -> null. prev (node 3) is the new head.

Optimization

Iterative three-pointer rewire

Walk the list once, flipping each next pointer to face backwards. Keep three references: prev (the already-reversed prefix, starting at null), curr (the node being rewired), and a saved next so we don't lose the rest of the list when we overwrite curr.next.

At each step: stash curr.next, point curr.next back at prev, then slide prev and curr forward one node. When curr falls off the end, prev is the new head.

O(n) time (one pass), O(1) space (only the three pointers).

function reverseList(head) {
  let prev = null;        // the reversed portion built so far (empty at first)
  let curr = head;        // the node we're about to rewire
  while (curr) {
    const next = curr.next; // save the rest of the list before we overwrite the link
    curr.next = prev;       // flip this node's pointer to face backwards
    prev = curr;            // the reversed portion now includes curr
    curr = next;            // advance into the still-forward portion
  }
  return prev;            // curr is null; prev is the last node visited = new head
}

Complexity analysis

Time complexity: O(n). Here's why:

The loop visits each of the n nodes exactly once.
Per node the work is O(1): save next, flip one pointer, advance two variables.

There's no nested traversal, so the whole reversal is a single pass — O(n).

Space complexity: O(1). Here's why:

Only three pointers (prev, curr, next) are kept, regardless of list length.
The nodes are rewired in place — no new list is allocated.

This is the win over the brute force, which built a second list and a values array for O(n) space.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
head = []null	[]null	Empty list — nothing to reverse, returns empty.
head = [1]1null	[1]1null	Single node is its own reverse.
head = [1,2]12null	[2,1]21null	Smallest case where pointers actually move.
head = [7,7,7]777null	[7,7,7]777null	All-equal values — reversed list looks identical, but every link was still flipped.
head = [1,2,3,4]1234null	[4,3,2,1]4321null	Even length.
head = [-1,0,2]-102null	[2,0,-1]20-1null	Negative and zero values reverse like any other.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor