Reverse Linked List
Problem statement
You are given the head of a singly linked list — a chain of nodes where each node holds a value and a pointer to the next node. Reverse the direction of every link so the last node becomes the new head and the first node becomes the new tail, and return the new head.
Nothing about the values changes — only the order the nodes point to each other in. An empty list or a list with a single node is already "reversed" as-is.
Examples
Example 1
Input: head = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]
Explanation: Every link is flipped, so the node that used to be last (5) becomes the new head, and the old head (1) becomes the new tail.

Example 2
Input: head = [1, 2]
Output: [2, 1]
Explanation: With two nodes there's only one link to flip; 2 now points to 1, and 1 points to nothing.

Example 3
Input: head = []
Output: []
Explanation: An empty list has no links to reverse, so the output is empty too.
Hints
next pointer should become, one node at a time.Approach
Optimal: Three pointers, iterative
Intuition
Walk the list once, and at each node flip its next pointer to point backward instead of forward. To do that safely you need three things in hand at once: the node you're fixing (curr), the node it should now point to (prev, the one before it), and the node you still need to visit next (saved before you overwrite curr.next). This is what makes it faster than recursion — no call stack, just three variables that move forward together.
Steps
- Set
prevto null andcurrtohead. - While
curris not null, savecurr.nextin a temporarynxt(or you'll lose the rest of the list). - Point
curr.nextback toprev. - Move
prevtocurr, andcurrtonxt. - When
currbecomes null,previs the new head — return it.
Dry run
head = [1, 2, 3, 4, 5]
| step | curr | nxt (saved) | curr.next set to | prev after |
|---|---|---|---|---|
| 1 | 1 | 2 | null | 1 |
| 2 | 2 | 3 | 1 | 2 |
| 3 | 3 | 4 | 2 | 3 |
| 4 | 4 | 5 | 3 | 4 |
| 5 | 5 | null | 4 | 5 |
curr is now null, so prev (node 5) is returned as the new head: 5 → 4 → 3 → 2 → 1.
Edge cases: an empty list never enters the loop and returns prev, which is still null; a single node flips its next to null (unchanged, since it had no next) and returns itself.
Complexity
Time O(n) - one pass over the list; every node's `next` pointer is updated exactly once.
Space O(1) - only three pointer variables are used, no matter how long the list is; nothing is copied and nothing is pushed onto a call stack.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head):
prev = None
curr = head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev
def build_list(values):
dummy = ListNode()
tail = dummy
for v in values:
tail.next = ListNode(v)
tail = tail.next
return dummy.next
def to_values(node):
out = []
while node:
out.append(node.val)
node = node.next
return out
if __name__ == "__main__":
print(to_values(Solution().reverseList(build_list([1, 2, 3, 4, 5]))))
print(to_values(Solution().reverseList(build_list([1, 2]))))
print(to_values(Solution().reverseList(build_list([]))))RecapThe whole problem in a few lines, for the night before
- Spot it: "reverse the direction of every pointer in a linked list"
- Idea: walk once with
prev/curr/next, flipping each node'snextto point atprev - Cost: O(n) time; O(1) space iteratively (O(n) stack recursively)
- Trap: overwriting
curr.nextbefore saving the real next node loses the rest of the list
Interview follow-ups
Reverse the list in groups of k nodes (e.g. every block of 3), leaving a shorter final block unreversed if there aren't enough nodes left.
Reuse the same three-pointer idea, but stop it after exactly k nodes instead of running it to the end. First walk ahead to check that k nodes actually exist (if not, leave that tail block alone); then reverse just that block, remember its new tail (the group's old head), and connect that tail's
nextto the head of the next reversed group. Still O(n) time; doing this recursively adds O(n/k) stack depth, while an iterative version keeps it at O(1) extra space.What if this were a doubly linked list instead of singly linked?
The core idea is the same — walk once and flip pointers — but now each node has two pointers to swap, not one. For every node, swap its
nextandprevreferences, then move forward using what was originallynext(before the swap). At the end, the old tail'sprevbecomes null and it is the new head. Still O(n) time, O(1) space.
Frequently asked questions
They do the same work in the same O(n) time, but the recursive version uses O(n) stack frames — one per node. A very long list (tens of thousands of nodes) can overflow the call stack in languages without tail-call optimization, like Python and Java, where iteration has no such limit and runs in constant extra space.
It's a fast, low-risk warm-up that checks whether a candidate can manipulate pointers correctly under a little time pressure — the same care needed for any manual reference management (freeing nodes safely, not losing track of "the rest" of a structure), which shows up whenever you work close to the metal in systems and infra code.
You overwrite your only pointer to the rest of the list, so curr = nxt on the next line reads the wrong value instead of the real next node — the loop stops early and every node after that mistake is lost for good.
It reuses the existing nodes and only rewrites their next pointers — no new nodes are allocated, unlike the brute-force approach, which builds a fresh list from copied values.
