TL;DR
Iterative three-pointer reversal — O(n) time, O(1) space. Recursion is the classic O(n)-stack alternative.
Approach 1 — Brute force: copy values, rebuild backwards
Walk the list once collecting values, then build a new list from those values in reverse.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:
vals = []
node = head
while node:
vals.append(node.val)
node = node.next
new_head = None
for v in vals:
new_head = ListNode(v, new_head)
return new_head
Complexity: O(n) time, O(n) space.
This passes the constraints, but it misses the point of the exercise: the interviewer wants the pointers of the existing nodes rewired in O(1) extra space, not a value copy.
Approach 2 — Iterative pointer reversal
Maintain an invariant with two pointers: prev heads the fully-reversed prefix, and curr heads the untouched suffix. Each step extends the invariant by one node: save curr.next, flip curr.next to point at prev, then advance both pointers. When curr runs off the end, prev is the new head.
The single step, flipping the link between prev and curr while nxt holds the rest of the list:
flowchart LR
prev([prev]) --> curr([curr])
curr --> nxt([nxt]) --> rest([...])
curr -. new link .-> prev
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:
prev = None
curr = head
while curr:
nxt = curr.next # save the rest of the list
curr.next = prev # flip the link
prev = curr # advance the reversed prefix
curr = nxt # advance into the suffix
return prev
Walkthrough on 1 -> 2 -> 3 -> 4 -> 5:
| step | reversed part (prev) | remaining part (curr) |
|---|
| start | ∅ | 1 -> 2 -> 3 -> 4 -> 5 |
| 1 | 1 | 2 -> 3 -> 4 -> 5 |
| 2 | 2 -> 1 | 3 -> 4 -> 5 |
| 3 | 3 -> 2 -> 1 | 4 -> 5 |
| 4 | 4 -> 3 -> 2 -> 1 | 5 |
| 5 | 5 -> 4 -> 3 -> 2 -> 1 | ∅ → return prev |
Complexity: O(n) time, O(1) space.
Approach 3 — Recursive reversal
Let the recursion reverse the sublist after head and return its new head. At that point head.next still points at what is now the tail of the reversed sublist, so head.next.next = head appends head behind it, and head.next = None marks the new tail.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import Optional
def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
new_head = reverseList(head.next)
head.next.next = head
head.next = None
return new_head
Walkthrough on 1 -> 2 -> 3: recursion dives to node 3 (base case, returned as new_head). Unwinding at node 2: 2.next is 3, so 3.next = 2 and 2.next = None, giving 3 -> 2. Unwinding at node 1: 1.next is 2 (now the tail), so 2.next = 1, 1.next = None, giving 3 -> 2 -> 1. new_head = 3 is passed up unchanged.
Complexity: O(n) time, O(n) space for the call stack. At the constraint’s 5000 nodes this exceeds Python’s default recursion limit of 1000, which is a concrete reason to prefer the iterative form.
Common pitfalls
- Flipping
curr.next before saving it: the rest of the list becomes unreachable and the loop ends after one node.
- Returning
curr (which is None when the loop exits) instead of prev.
- In the recursive version, forgetting
head.next = None: the old head keeps a forward link and the list ends in a 2-cycle.
- Assuming a non-empty list: both versions must return
None untouched for an empty input. The base case and loop condition above already handle this.
Pattern takeaway
In-place linked-list manipulation follows one discipline: save the pointer you are about to overwrite, then rewire. The prev/curr/nxt three-pointer walk is the core building block, reused later in “reverse in k-groups”, “reorder list”, and palindrome checks.