Reverse Linked List

1. Define the problem

Given the head of a singly linked list, reverse the list and return the new head. Use recursion : the base case is a node with no next node — return it as-is. The recursive case reverses everything after the current node first, then fixes the current node’s two pointers on the way back up the call stack .

Constraints

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

Example

Inputhead = [1, 2, 3, 4, 5]

Output[5, 4, 3, 2, 1]

Explanation Every node’s next pointer is flipped, so the list now runs from tail to head.

2. Know the words first

In plain terms

Base case: The smallest version of the problem, simple enough to answer directly without recursing further.
Call stack: The pending calls, each waiting for its own recursive call to return before it can finish its own work.

3. Visualize the solution

Recurse to the end, then relink pointers on the way back up

Statusreverse(1)

Call reverse on node 1 (index 0). It must reverse everything after it before it can do anything.

What happens in this step

reverse(1) calls reverse(2)

Node 1's next is node 2, and node.next !== null, so this is the recursive case: reverse(1) must wait for reverse(2) to return before it can fix any pointers.

Step 1 of 10

Steps to visualize

Call reverse on the head node — it has to reverse everything after it before it can finish.
Keep recursing forward until the base case: a node with no next node.
Each call waits on the call stack for its recursive call to return.
As calls return, flip the pointer: node.next.next = node, then node.next = null.
Unwind back to the original head, which now returns the new head of the reversed list.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Recurse to the end, then relink pointers on the way back up

Statusreverse(1)

Call reverse on node 1 (index 0). It must reverse everything after it before it can do anything.

What happens in this step

reverse(1) calls reverse(2)

Node 1's next is node 2, and node.next !== null, so this is the recursive case: reverse(1) must wait for reverse(2) to return before it can fix any pointers.

Step 1 of 10

5. Solution

Solution

solution.tsTypeScript

function reverseList(values) {
  function buildList(arr) {
    const dummy = { val: 0, next: null };
    let curr = dummy;
    for (const v of arr) {
      curr.next = { val: v, next: null };
      curr = curr.next;
    }
    return dummy.next;
  }

  function toArray(node) {
    const result = [];
    while (node) {
      result.push(node.val);
      node = node.next;
    }
    return result;
  }

  function reverse(node) {
    if (node === null || node.next === null) {
      return node; // base case
    }
    const newHead = reverse(node.next); // recursive case
    node.next.next = node;
    node.next = null;
    return newHead;
  }

  return toArray(reverse(buildList(values)));
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`head = [1, 2, 3, 4, 5]`	`[5, 4, 3, 2, 1]`	example from the docstring
`head = []`	`[]`	empty list is the immediate base case
`head = [7]`	`[7]`	a single node is already a base case, no recursion needed
`head = [1, 2]`	`[2, 1]`	smallest non-trivial case, one recursive call deep
`head = [3, 3, 3]`	`[3, 3, 3]`	repeated values still reverse correctly
`head = [-1, -2, -3]`	`[-3, -2, -1]`	negative values reverse correctly
`head = [1, 2, 3, 4, 5, 6, 7]`	`[7, 6, 5, 4, 3, 2, 1]`	a longer list, several calls deep on the stack

Reverse Linked List