Reverse Linked List

Problem

Reverse a singly linked list and return the new head. Do it in-place with O(1) extra space.

Input:  1 -> 2 -> 3 -> 4 -> 5 -> None
Output: 5 -> 4 -> 3 -> 2 -> 1 -> None
 
Input:  1 -> 2 -> None
Output: 2 -> 1 -> None
 
Input:  None  →  None

Solution

Approach: Three-pointer in-place reversal.

Walk the list once with three handles: prev (the already-reversed prefix, starting at None), curr (the node being processed), and next_node (a temporary stash). The loop invariant is that everything from prev backward already points the right way, and curr onward still points forward. Each iteration flips exactly one link. The order of the four statements is what makes it work: first stash next_node = curr.next, because the very next line curr.next = prev overwrites that pointer and would otherwise strand the entire rest of the list with no way to reach it. Then advance both handles forward with prev, curr = curr, next_node.

Trace 1 -> 2 -> 3. Start prev=None, curr=1. Iteration one: stash 2, point 1 -> None, advance to prev=1, curr=2. Iteration two: stash 3, point 2 -> 1, advance to prev=2, curr=3. Iteration three: stash None, point 3 -> 2, advance to prev=3, curr=None. The loop exits because curr is None, and prev now holds node 3, the old tail and new head, so we return it.

Edge cases: An empty list (head is None) skips the loop entirely and returns prev = None. A single node redirects its already-None next to None and returns itself unchanged.

Complexity: O(n) time, O(1) space - one pass, three pointer variables regardless of length.