Reverse Linked List

Examples

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

Input: head = [1, 2]
Output: [2, 1]

Input: head = []
Output: []

An empty list reversed is still empty.

Constraints

• The number of nodes is between 0 and 5000.

• -5000 <= Node.val <= 5000

Approach

Walking through the list and flipping one pointer at a time works, but you have to be careful about order: once you overwrite a node's next pointer, you can't get to what used to come after it unless you saved that reference first.

The clean way is to carry three references as you walk: the node before the current one (initially nothing), the current node, and (temporarily) the node after it. At each step you point the current node backward, then shift all three references one step forward. The same idea can also be expressed recursively, reversing the rest of the list first and then fixing up the one link at the very front.

Solutions

Recursive Reversal

Trust that reversing everything after the current node already works (that's the recursive leap of faith), and just fix up the link between the current node and the rest.

Once the rest of the list is reversed, the node right after the current one is now the last node of that reversed piece. So you make that node point back at the current node, and cut the current node's own forward pointer.

This is elegant to read, but each recursive call sits on the call stack until the whole list has been walked, so it uses memory proportional to the length of the list.

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function reverseList(head) {
  if (head === null || head.next === null) {
    return head;
  }

  const newHead = reverseList(head.next);

  // head.next is currently the last node of the already-reversed rest.
  // Make it point back at head, then clear head's old forward link.
  head.next.next = head;
  head.next = null;

  return newHead;
}

Time: O(n) · Space: O(n) — call stack depth equals list length

Optimal — Iterative Pointer Rewiring

Walk the list exactly once, keeping a running "previous" pointer that starts at null. At each node, save its next pointer before touching anything, then point the current node back at "previous", then slide both "previous" and "current" one step forward.

When "current" finally runs off the end of the list, "previous" is sitting on the old last node — which is exactly the new head.

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function reverseList(head) {
  let prev = null;
  let curr = head;

  while (curr !== null) {
    const next = curr.next; // save before we overwrite curr.next
    curr.next = prev;       // flip the pointer
    prev = curr;            // advance prev
    curr = next;            // advance curr
  }

  return prev; // prev now points at the old tail — the new head
}

Time: O(n) · Space: O(1)