What if the linked list is empty?

If the list is empty, `head` is `null`. The pointer `curr` initializes to `null`, the loop condition fails immediately, and the function returns `prev` (which is `null`). This correctly handles the edge case.

What if the list has only one node?

The loop runs exactly once. The single node's next pointer is set to `null`, and `prev` becomes that node. The function returns `prev`, leaving the one-node list unchanged as expected.

Can this be done recursively?

Yes. A recursive approach reverses the sublist starting at `head.next`, then appends the current `head` to the end of that reversed sublist. However, recursion requires $O(n)$ auxiliary space for the call stack, whereas the iterative method requires $O(1)$ space.

How to reverse a linked list

Reversing a singly linked list requires iterating through the nodes and changing each node's next pointer to point to the previous node. This iterative method applies when you need an in-place reversal with $O(n)$ time complexity and $O(1)$ space complexity.

The setup

Initialize three node pointers. Set prev to null. Set curr to the head of the list. Set next_node to null.

The steps

Loop while curr is not null. 2. Inside the loop, temporarily store the next node: next_node = curr.next. 3. Reverse the current node's pointer: curr.next = prev. 4. Advance the prev pointer one step: prev = curr. 5. Advance the curr pointer one step: curr = next_node. 6. After the loop terminates, update the head of the list to be prev.

Checking the result

Verify that the new head is the original tail of the list. Ensure that the original head node now points to null (acting as the new tail). Traversing from the new head must visit all original nodes in exactly the reverse order without infinite loops.

Common errors

The most frequent error is failing to store curr.next before overwriting it. If curr.next = prev is executed before saving the next node, the remainder of the list is permanently lost. Another common error is forgetting to update the original head pointer to point to prev at the end.

Worked example

Reverse the singly linked list: 1 -> 2 -> 3 -> null

Initial state: head = 1, prev = null, curr = 1, next_node = null. Iteration 1: next_node = 2 (save next). curr.next = null (reverse pointer). prev = 1 (advance prev). curr = 2 (advance curr). Iteration 2: next_node = 3. curr.next = 1. prev = 2. curr = 3. Iteration 3: next_node = null. curr.next = 2. prev = 3. curr = null. The loop terminates because curr is null. Set head = prev (which is 3). The new list is 3 -> 2 -> 1 -> null.

FAQ

Run your own problem

Answer form

References: Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein) · Algorithm Design Manual (Skiena) · Khan Academy: Computer Science Algorithms