Reverse Linked List

Problem in Plain English

Given the head of a singly linked list, flip every next pointer so the list runs in the opposite order, and return the new head.

Problem Statement

Given the head of an acyclic singly linked list, reverse the direction of every next link and return the new head. An empty list returns null.

Reuse every original node and preserve its value. The original tail becomes the new head, the original head becomes the null-terminated tail, and the caller must use the returned head to traverse the complete result.

Constraints

The number of nodes satisfies $0 \le n \le 5000$ .
Each node value satisfies $-5000 \le \mathrm{Node.val} \le 5000$ .
The input is acyclic; preserve the original node objects and values while reversing their links.

Examples

Example 1

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

Reverse all four original links and terminate node 1 with null. Return the original node 5, so traversing from the returned head visits the original nodes in reverse order.

Example 2

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

Point node 2 to node 1 and clear node 1 next. Returning the old head would expose only node 1 rather than both nodes.

Example 3

Input: head = []
Output: []

There is no node or link to change. Both approaches return null immediately without allocating an output node.

Example 4

Input: head = [4]
Output: [4]

The sole node is already the head and null-terminated tail. The returned reference is the same object.

Example 5

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

The original last node comes first even though several values are equal. Correct reversal changes node order and links while preserving each node value.

Intuition

A node cannot point backward until we remember the node before it. For Example 1, save the link from 1 to 2, point 1 at null, then save the link from 2 to 3 and point 2 at 1. This grows a reversed prefix while keeping the untouched suffix reachable. Recursion reaches the old tail first and performs the same link repair while calls return; iteration stores the needed references directly and avoids a call stack.

Approaches

Recursive Reversal

Solution Details

Reveal Recursive Reversal: intuition, complexity, and code

Intuition

Reverse the suffix recursively, then attach the current head after its original successor. In Example 1 the deepest call returns node 5; the call for node 4 then links 5 back to 4 and clears 4 next. Each returning call adds one earlier node to the tail, while the same new head propagates all the way out.

Step-by-Step Logic

Return head when it is null or has no successor. Otherwise recursively reverse the suffix from head.next. For Example 1 the calls descend through 1, 2, 3, 4 and reach the singleton 5.
Keep the returned newHead unchanged. At node 4, it is node 5, and the original successor of 4 is now the tail of the reversed suffix.
Point that original successor back to the current head, then clear the current head next link to avoid a cycle. At node 4, write 5.next = 4 and 4.next = null.
Apply the same repair as each earlier call returns. At nodes 3, 2 and 1, append that node after its original successor and clear its old forward link.
Return the same new head through every frame. Example 1 returns node 5, exposing [5,4,3,2,1]. The Python wrapper raises the recursion limit for the stated bound and restores it once recursion finishes.

Why It Works

For an empty list or a singleton, returning the input already gives the correct reversed list. For a longer acyclic list, assume the recursive call correctly reverses the suffix beginning at head.next, using the same nodes and ending at that original successor. The current head is outside this suffix, and its old next reference still identifies the suffix tail. Assigning head.next.next = head appends the current head after that tail. Clearing head.next then removes the old forward link, breaking the temporary two-node cycle and making the appended head the new null-terminated tail. The returned suffix head is unchanged, so induction proves the final result contains exactly all original nodes in reverse order, with their values preserved.

Dry Run

Recursive Reversal: variable states at each step
Call action	Current head	Original successor	newHead	Link repair	Reversed suffix after return
Descend	1	2	pending	none	pending
Descend	2	3	pending	none	pending
Descend	3	4	pending	none	pending
Descend	4	5	pending	none	pending
Base case	5	null	5	none	5 -> null
Unwind	4	5	5	5.next = 4; 4.next = null	5 -> 4 -> null
Unwind	3	4	5	4.next = 3; 3.next = null	5 -> 4 -> 3 -> null
Unwind	2	3	5	3.next = 2; 2.next = null	5 -> 4 -> 3 -> 2 -> null
Unwind and return	1	2	5	2.next = 1; 1.next = null	[5,4,3,2,1]

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

Each node enters one recursive call and performs constant link work while returning, so time is linear. The live call frames store one head and successor context per node, using linear auxiliary space even though no ListNode copies are allocated. Python temporarily raises its recursion limit; Java and JavaScript require a runtime stack large enough for the input depth. Iteration is preferable when stack capacity is uncertain.

Code

Solution.java

1class ListNode {2    int val;3    ListNode next;4    ListNode(int val) { this.val = val; }5}6class Solution {7    public ListNode reverseList(ListNode head) {8        if (head == null || head.next == null) return head;9        ListNode newHead = reverseList(head.next);10        // The original successor is now the reversed suffix tail; append head there.11        head.next.next = head;12        // Remove the old forward link to break the temporary two-node cycle.13        head.next = null;14        return newHead;15    }16}

Hints

Hint 1

Track the node behind you with a prev pointer as you walk forward.

Hint 2

Save curr.next before overwriting it, or the rest of the list becomes unreachable.

Hint 3

Recursively, assume the suffix is already flipped and only repair the link between the head and its successor.

Edge Cases

An empty list returns null, and a singleton returns the same node with its null next link.
A two-node list needs both the backward link and a null old-head link; omitting the latter makes a cycle.
Negative or repeated values do not affect reversal, which is defined by node position and identity.
At 5000 nodes, recursion uses 5000 nested frames. The Python wrapper adjusts its limit, but Java and JavaScript stack capacity remains runtime-dependent; the iterative method needs no stack adjustment.
Any other reference to an input node observes changed links after this in-place operation. An old head reference now identifies only the new tail.

Common Mistakes and Interview Tips

Overwriting curr.next before saving its successor loses access to the untouched suffix.
Returning curr after the iterative loop returns null; return prev and assign that returned head in the caller.
In recursion, attaching head backward without clearing its old next creates a cycle between head and its original successor.
Calling recursion a constant-space method because no nodes are allocated ignores the linear call stack.
Reversing only values or constructing copies does not preserve the required original-node ordering; validate object references when values repeat.
Explain the reversed-prefix invariant in an interview and choose iteration for large or unknown depths rather than relying on a language default stack limit.

Key Takeaway

List rewiring comes down to saving the next link before overwriting it; that one habit prevents almost every lost-node bug.