LeetCode · #206

Reverse Linked List Solution

Given the head of a singly linked list, reverse the list and return the new head.

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #206

🏗️

Pattern

Reversal — iterative three-pointer

Given the head of a singly linked list, reverse the list and return the reversed list's head.

Example

 Input: 1 → 2 → 3 → 4 → 5 Output: 5 → 4 → 3 → 2 → 1 

Constraints

• 0 ≤ number of nodes ≤ 5000 • -5000 ≤ Node.val ≤ 5000

Section Two · Approach 1

Stack / Array — O(n) extra space

Push all nodes onto a stack, then pop them to build the reversed list. Correct but uses O(n) extra space. The iterative approach reverses pointers in-place with O(1) space.

Problem: O(n) extra space for the stack. We can reverse by simply flipping each node's next pointer to point backward — no extra storage needed.

Section Three · Approach 2

Iterative Three-Pointer — O(n) time, O(1) space

Maintain three pointers: prev, curr, and next. At each step, save the next node, reverse the current node's pointer to point at prev, then advance both prev and curr forward.

💡 Mental model: Imagine a conga line. You walk down the line and tell each person to turn around and face the person behind them. You need to remember who was next before you make someone turn (otherwise they lose track of the rest of the line). That's the next = curr.next save before flipping.

Algorithm

Step 1: prev = null, curr = head.
Step 2: While curr ≠ null:
next = curr.next (save)
curr.next = prev (reverse)
prev = curr (advance prev)
curr = next (advance curr)
Step 3: Return prev (new head).

🎯 This pattern is a building block:

Reversing a linked list (or a portion of it) appears as a sub-routine in LC 143 (Reorder List), LC 92 (Reverse Linked List II), LC 25 (Reverse Nodes in k-Group), and LC 234 (Palindrome Linked List).
Master this first.

Section Four · Trace

Visual Walkthrough

Trace through 1 → 2 → 3 → null:

Three-pointer reversal — flip one link per step

Section Five · Implementation

Code — Java & Python

Java — Iterative

 class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next; // save
curr.next = prev; // reverse
prev = curr; // advance prev
curr = next; // advance curr
}
return prev;
    }
}

Python — Iterative

 class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, curr = None, head
while curr:
            curr.next, prev, curr = prev, curr, curr.next
return prev

Recursive approach

Java — Recursive

 class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverseList(head.next);
        head.next.next = head; // reverse the link
head.next = null; // old forward link → null return newHead;
    }
}

Python — Recursive

 class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next: return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None return new_head

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Recursive	O(n)	O(n)	Elegant but O(n) call stack
Iterative ← optimal	O(n)	O(1)	Three pointers, in-place reversal

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Empty list	`null`	curr starts null → loop doesn't execute → return null.
Single node	`1 → null`	One iteration: 1.next=null, prev=1 → return 1.
Two nodes	`1 → 2`	Test minimum swap. Result: 2 → 1 → null.

⚠ Common Mistake: Forgetting to save curr.next before overwriting it. After curr.next = prev, the original forward link is lost. Without the next save, you can't advance to the rest of the list — the traversal breaks.

← Back to Linked List problems

LearningTree

LC 206 · Reverse Linked List — Solution & Explanation | DSA Guide