Reverse a Linked List — Iterative and Recursive in Java

Q: Reverse a Linked List — Iterative and Recursive in Java

**Iterative approach (preferred)**: use three pointers — `prev`, `curr`, `next` — and reverse one link at a time. Start with `prev = null, curr = head`; at each step save `next = curr.next`, flip `curr.next = prev`, then advance `prev = curr; curr = next`. When `curr == null`, `prev` is the new head. **Time O(n), Space O(1)**. **Recursive approach**: recursively reverse the rest of the list (`newHead = reverse(head.next)`), then flip the current node's pointers (`head.next.next = head; head.next = null`). **Time O(n), Space O(n) for recursion stack**. For interviews, always **start with iterative** because it's O(1) space and more production-safe (no stack overflow on large lists). Use recursive if specifically asked or for elegance. **Both must handle edge cases**: empty list (`head == null` → return null), single node (`head.next == null` → return head). **Common variants**: reverse a sublist `[m, n]` (add dummy head; reverse the middle segment; reconnect); reverse in groups of K (iteratively reverse each K-block; harder); reverse a doubly-linked list (swap prev/next at each node — simpler than singly). **Common bugs**: losing the rest of the list (must save `next` before flipping); forgetting to null out the new tail's `.next` in recursion (would create a cycle); not returning the new head. For **Java 21+** streaming contexts, avoid `Collectors.toList()` reversal tricks; stick to classical pointer manipulation. **Stack-safe recursion** via explicit iteration is always the right production choice.

Intermediate·6 min read·

AmazonGoogleMetaMicrosoftApple

Fast recall

Quick revision

Core answer

Iterative approach (preferred): use three pointers — prev, curr, next — and reverse one link at a time. Start with prev = null, curr = head; at each step save next = curr.next, flip curr.next = prev, then advance prev = curr; curr = next. When curr == null, prev is the new head. Time O(n), Space O(1). Recursive approach: recursively reverse the rest of the list (newHead = reverse(head.next)), then flip the current node's pointers (head.next.next = head; head.next = null). Time O(n), Space O(n) for recursion stack. For interviews, always start with iterative because it's O(1) space and more production-safe (no stack overflow on large lists). Use recursive if specifically asked or for elegance. Both must handle edge cases: empty list (head == null → return null), single node (head.next == null → return head). Common variants: reverse a sublist [m, n] (add dummy head; reverse the middle segment; reconnect); reverse in groups of K (iteratively reverse each K-block; harder); reverse a doubly-linked list (swap prev/next at each node — simpler than singly). Common bugs: losing the rest of the list (must save next before flipping); forgetting to null out the new tail's .next in recursion (would create a cycle); not returning the new head. For Java 21+ streaming contexts, avoid Collectors.toList() reversal tricks; stick to classical pointer manipulation. Stack-safe recursion via explicit iteration is always the right production choice.

Interview Answer6 min

Iterative reversal — the standard approach

Three pointers: prev, curr, next

Start: prev = null, curr = head
Each iteration:
- Save next = curr.next (don't lose the rest)
- Flip: curr.next = prev
- Advance: prev = curr; curr = next
When curr is null: return prev (new head)

Time O(n), Space O(1)

Why iterative is preferred

O(1) space (just three pointers)
No stack overflow risk
Easy to adapt for variants
Production-safe for any list size

Walkthrough on 1 → 2 → 3

Iter 1: next=2, 1.next=null, prev=1, curr=2. List: null ← 1, 2 → 3.

Iter 2: next=3, 2.next=1, prev=2, curr=3. List: null ← 1 ← 2, 3.

Iter 3: next=null, 3.next=2, prev=3, curr=null. List: null ← 1 ← 2 ← 3.

Return prev=3.

Recursive reversal

Base case: head == null or head.next == null → return head
Recursive: newHead = reverse(head.next)
Flip: head.next.next = head; head.next = null
Return newHead

How it works

Recursion reaches the tail, which becomes the new head
Unwinding: each node flips its .next.next to itself, then nulls its own .next
Keeps passing the same newHead up

Time O(n), Space O(n) — stack frames

Stack overflow risk

Default Java stack ~10K frames
reverse(10000) throws StackOverflowError
Use iterative for long lists

Edge cases

Empty: head == null → return null
Single node: return head
Two nodes: correctly reversed

Reverse sublist [m, n]

Use dummy head to uniformly handle m=1
Advance to node before m (preStart)
Reverse the segment (standard iterative)
Reconnect: preStart.next.next = segment.tail.next; preStart.next = new segment head
O(n) time, O(1) space

Reverse K-group

Iterate, take groups of K
Reverse each group
Thread back together with dummy head
If fewer than K remain, leave as-is
O(n) time, O(1) space

Doubly-linked list reversal

Swap prev/next at each node
Then the old tail becomes new head
Simpler than singly-linked (both pointers always set)

Common bugs

1. Losing the rest of the list

Forgetting to save next before flipping
Always: next = curr.next FIRST

2. Creating a cycle (recursive)

Forgetting head.next = null
Traversing the reversed list loops forever

3. Not returning new head

Return prev (iterative) or newHead (recursive)
Not head (now at null or tail)

4. Off-by-one in sublist version

Advance preStart m-1 times (to node before m)
Not m times

5. Modifying wrong pointer

curr.next = prev (flip current node's link)
Not prev.next = curr
Draw a diagram if unsure

Related problems

Palindrome linked list

Find middle (slow/fast)
Reverse second half
Compare first half and reversed second half
O(n) time, O(1) space

Add two numbers (lists)

If stored least-significant-digit-first: just iterate
If most-significant-first: reverse, add, reverse (or use stack)

Swap pairs / reverse in pairs

Special case of K-group with K=2

Iterative recipe to remember

1
prev=null, curr=head
2
while curr != null:
- next = curr.next
- curr.next = prev
- prev = curr
- curr = next
3
return prev

Recursive recipe

1
If head null or head.next null: return head
2
newHead = reverse(head.next)
3
head.next.next = head
4
head.next = null
5
return newHead

Recommendation: Always start with the iterative approach — it's O(1) space, has no stack-overflow risk, and extends naturally to variants (reverse sublist, K-group reversal, pair swap). Memorize the three-pointer recipe: save next, flip link, advance prev and curr. Draw the list with pointer labels when coding; this catches 90% of bugs before they happen. The recursive approach is elegant but has O(n) stack space and fails on long lists (~10K+ nodes default Java stack); mention it as an alternative when asked, but recommend iterative for production. The three critical pointer moves in the recursive version are: newHead = reverse(head.next) (recurse on the rest), head.next.next = head (make the next node point back to current), head.next = null (current becomes new tail). Forgetting the last line creates a cycle. For variants, use a dummy head to uniformly handle edge cases where the head itself changes (sublist reversal starting at m=1, K-group reversal). For doubly-linked lists, just swap prev/next at each node — simpler than singly-linked. Related problems like palindrome linked list and Kth from end build on these pointer-manipulation skills. The mental model: reverse = flip each link one at a time, carefully tracking where each node points. Once you can draw the transformation on a whiteboard, the code writes itself.

Interview-ready guide

Interview answer