DSA problem
Reverse Linked List
Given the head of a singly linked list, reverse the list and return the new head. The reversal must be done by rewiring the next pointers of the existing nodes — no new list should be constructed and no auxiliary array should be used.
The fundamental challenge is that a singly linked list only points forward. Once you advance past a node, you have no way to get back to it. So the algorithm must, before moving on from each node, capture enough information to flip its next pointer toward the node it just came from.
The classic iterative solution uses three pointers: prev, curr, and next. prev starts at null (the new tail of the reversed list), and curr starts at head. At each step, save curr.next into next, flip curr.next to point at prev, then advance both prev and curr one step forward. When curr falls off the end, prev is the new head.
This is a foundational pattern — most other in-place reversal problems (reverse a sublist, reverse in k-groups, palindrome check) reduce to applying this exact micro-algorithm to a window of nodes. The whole reversal runs in O(n) time visiting each node once, and O(1) extra space because only three pointer variables are used. A recursive solution is also common but uses O(n) call-stack space.
Examples
head = [1,2,3,4,5][5,4,3,2,1]head = [1,2][2,1]head = [][]Constraints
- The number of nodes in the list is the range [0, 5000].
- -5000 <= Node.val <= 5000
- Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.