90. Reverse Linked List

🔗 LeetCode Problem: 206. Reverse Linked List
📊 Difficulty: Easy
🏷️ Topics: Linked List, Recursion

Problem Statement

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

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Visual:
Before: 1 → 2 → 3 → 4 → 5 → null
After:  5 → 4 → 3 → 2 → 1 → null

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints: - The number of nodes in the list is in the range [0, 5000]. - -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

🌟 ELI5: The Simple Idea!

Think of reversing a train:

You have train cars connected:
  [1] → [2] → [3] → [4] → [5] → null

To reverse, you need to:
  1. Make [1] point to null (it becomes the tail)
  2. Make [2] point to [1]
  3. Make [3] point to [2]
  4. Make [4] point to [3]
  5. Make [5] point to [4] (it becomes the head)

Result:
  [5] → [4] → [3] → [2] → [1] → null

The Key Challenge:

When you reverse [2]'s pointer to [1]:
  [1] ← [2]   [3] → [4] → [5]

You LOSE access to [3]!

Solution: SAVE the next pointer BEFORE reversing!

🎨 Visual Understanding

The Reversal Process

Initial:
  null    1 → 2 → 3 → 4 → 5 → null
  ↑       ↑
 prev   curr

Step 1: Reverse 1's pointer
  null ← 1    2 → 3 → 4 → 5 → null
         ↑    ↑
       prev curr

Step 2: Reverse 2's pointer
  null ← 1 ← 2    3 → 4 → 5 → null
              ↑    ↑
            prev curr

Step 3: Reverse 3's pointer
  null ← 1 ← 2 ← 3    4 → 5 → null
                  ↑    ↑
                prev curr

Step 4: Reverse 4's pointer
  null ← 1 ← 2 ← 3 ← 4    5 → null
                      ↑    ↑
                    prev curr

Step 5: Reverse 5's pointer
  null ← 1 ← 2 ← 3 ← 4 ← 5    null
                          ↑    ↑
                        prev curr

curr is null, done!
prev is new head → return prev

🎯 Approach 1: Iterative (Recommended) ⭐

The Most Common Interview Solution

Core Logic:

Three pointers:
  - prev: Previous node (starts as null)
  - curr: Current node (starts at head)
  - next: Next node (saved before reversing)

For each node:
  1. Save next: next = curr.next
  2. Reverse pointer: curr.next = prev
  3. Move forward: prev = curr, curr = next

Implementation

/**
 * Iterative reversal
 * Time: O(n), Space: O(1)
 */
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;

    while (curr != null) {
        ListNode next = curr.next;  // CRITICAL: Save before changing!
        curr.next = prev;           // Reverse the pointer
        prev = curr;                // Move prev forward
        curr = next;                // Move curr forward
    }

    return prev;  // prev is new head
}

⏰ Time: O(n) - Visit each node once
💾 Space: O(1) - Only three pointers

🔍 Super Detailed Dry Run

Example: head = [1, 2, 3, 4, 5]

Goal: Reverse to [5, 4, 3, 2, 1]

Initial state:
  head → 1 → 2 → 3 → 4 → 5 → null

  prev = null
  curr = head (node 1)

═══════════════════════════════════════════════════════════════
Iteration 1: Process node 1
═══════════════════════════════════════════════════════════════

State before:
  null    1 → 2 → 3 → 4 → 5 → null
  ↑       ↑
 prev   curr

Step 1: Save next
  next = curr.next
  next = node 2

  null    1 → 2 → 3 → 4 → 5 → null
  ↑       ↑   ↑
 prev   curr next

Step 2: Reverse pointer
  curr.next = prev
  node 1's next = null

  null ← 1    2 → 3 → 4 → 5 → null
  ↑      ↑    ↑
 prev  curr next

Step 3: Move prev forward
  prev = curr
  prev = node 1

  null ← 1    2 → 3 → 4 → 5 → null
         ↑    ↑
       prev next
       curr

Step 4: Move curr forward
  curr = next
  curr = node 2

  null ← 1    2 → 3 → 4 → 5 → null
         ↑    ↑
       prev curr

═══════════════════════════════════════════════════════════════
Iteration 2: Process node 2
═══════════════════════════════════════════════════════════════

State before:
  null ← 1    2 → 3 → 4 → 5 → null
         ↑    ↑
       prev curr

Step 1: Save next
  next = curr.next
  next = node 3

  null ← 1    2 → 3 → 4 → 5 → null
         ↑    ↑   ↑
       prev curr next

Step 2: Reverse pointer
  curr.next = prev
  node 2's next = node 1

  null ← 1 ← 2    3 → 4 → 5 → null
         ↑   ↑    ↑
            prev next
            curr

Step 3: Move prev forward
  prev = curr
  prev = node 2

  null ← 1 ← 2    3 → 4 → 5 → null
              ↑    ↑
            prev next
            curr

Step 4: Move curr forward
  curr = next
  curr = node 3

  null ← 1 ← 2    3 → 4 → 5 → null
              ↑    ↑
            prev curr

═══════════════════════════════════════════════════════════════
Iteration 3: Process node 3
═══════════════════════════════════════════════════════════════

State before:
  null ← 1 ← 2    3 → 4 → 5 → null
              ↑    ↑
            prev curr

Steps (same pattern):
  next = node 4
  curr.next = prev (3 points to 2)
  prev = node 3
  curr = node 4

State after:
  null ← 1 ← 2 ← 3    4 → 5 → null
                  ↑    ↑
                prev curr

═══════════════════════════════════════════════════════════════
Iteration 4: Process node 4
═══════════════════════════════════════════════════════════════

State before:
  null ← 1 ← 2 ← 3    4 → 5 → null
                  ↑    ↑
                prev curr

Steps:
  next = node 5
  curr.next = prev (4 points to 3)
  prev = node 4
  curr = node 5

State after:
  null ← 1 ← 2 ← 3 ← 4    5 → null
                      ↑    ↑
                    prev curr

═══════════════════════════════════════════════════════════════
Iteration 5: Process node 5
═══════════════════════════════════════════════════════════════

State before:
  null ← 1 ← 2 ← 3 ← 4    5 → null
                      ↑    ↑
                    prev curr

Steps:
  next = curr.next = null
  curr.next = prev (5 points to 4)
  prev = node 5
  curr = null

State after:
  null ← 1 ← 2 ← 3 ← 4 ← 5    null
                          ↑    ↑
                        prev curr

═══════════════════════════════════════════════════════════════
Loop Exit
═══════════════════════════════════════════════════════════════

Condition: while (curr != null)
  curr = null, exit loop

Return: prev (node 5)

Final list:
  5 → 4 → 3 → 2 → 1 → null ✓

Result: [5, 4, 3, 2, 1]

🎯 Approach 2: Recursive (Elegant) ⭐

The Elegant Solution

Core Logic:

Recursively reverse the rest of the list
Then fix the pointers for current node

Base case: null or single node
Recursive case:
  1. Reverse rest of list
  2. Make next node point back to current
  3. Make current point to null

Implementation

/**
 * Recursive reversal
 * Time: O(n), Space: O(n) - recursion stack
 */
public ListNode reverseList(ListNode head) {
    // Base case: empty or single node
    if (head == null || head.next == null) {
        return head;
    }

    // Recursively reverse rest of list
    ListNode newHead = reverseList(head.next);

    // Fix pointers for current node
    head.next.next = head;  // Make next node point back
    head.next = null;       // Remove forward pointer

    return newHead;  // Return new head (unchanged through recursion)
}

⏰ Time: O(n) - Visit each node once
💾 Space: O(n) - Recursion call stack

🔍 Recursive Dry Run

Example: head = [1, 2, 3]

Goal: Reverse to [3, 2, 1]

═══════════════════════════════════════════════════════════════
Call Stack Building Phase
═══════════════════════════════════════════════════════════════

reverseList(1 → 2 → 3 → null)
  ↓ head = 1, head.next = 2
  ↓ Not base case, recurse

  reverseList(2 → 3 → null)
    ↓ head = 2, head.next = 3
    ↓ Not base case, recurse

    reverseList(3 → null)
      ↓ head = 3, head.next = null
      ↓ BASE CASE! Return head (3)
      return 3

    [Back to reverseList(2 → 3 → null)]
    newHead = 3

    Current state:
      1 → 2 → 3 → null
          ↑   ↑
        head newHead

    Fix pointers for node 2:
      head.next.next = head
      → node 3's next = node 2
      → 3 → 2

      head.next = null
      → node 2's next = null
      → 2 → null

    Now: 1 → 2 ← 3
            ↓
           null

    return newHead (3)

  [Back to reverseList(1 → 2 → 3 → null)]
  newHead = 3

  Current state:
    1 → 2 ← 3
        ↓
       null
    ↑
  head

  Fix pointers for node 1:
    head.next.next = head
    → node 2's next = node 1
    → 2 → 1

    head.next = null
    → node 1's next = null
    → 1 → null

  Final: 1 ← 2 ← 3
         ↓
        null

  return newHead (3)

═══════════════════════════════════════════════════════════════
Result
═══════════════════════════════════════════════════════════════

Final list: 3 → 2 → 1 → null ✓

Visual of Recursion:

Original: 1 → 2 → 3 → null

After reverseList(3): returns 3
  1 → 2 → 3 → null
          ↑
      newHead = 3

After fixing 2's pointers:
  1 → 2 ← 3
      ↓
     null

After fixing 1's pointers:
  1 ← 2 ← 3
  ↓
 null

Return 3 as final head

🎯 Comparison of Approaches

Approach          Time    Space   Notes
═══════════════════════════════════════════════════════════════
Iterative         O(n)    O(1)    Most common in interviews
Recursive         O(n)    O(n)    Elegant but uses stack space

Recommended: Iterative
  ✓ More efficient (O(1) space)
  ✓ Easier to trace
  ✓ No stack overflow risk

But know both!
  Recursive shows understanding of recursion
  Good follow-up answer

⚠️ Common Mistakes to Avoid

Mistake 1: Not saving next pointer

// ❌ WRONG - Lost reference!
while (curr != null) {
    curr.next = prev;  // Lost access to rest of list!
    prev = curr;
    curr = curr.next;  // curr.next is now prev!
}

// ✓ CORRECT - Save first!
while (curr != null) {
    ListNode next = curr.next;  // Save before changing
    curr.next = prev;
    prev = curr;
    curr = next;  // Use saved pointer
}

Mistake 2: Returning curr instead of prev

// ❌ WRONG - curr is null at end!
while (curr != null) {
    // ...
}
return curr;  // Returns null!

// ✓ CORRECT - prev is last node processed
return prev;  // New head

Mistake 3: Forgetting to set head.next to null in recursion

// ❌ WRONG - Creates cycle!
ListNode newHead = reverseList(head.next);
head.next.next = head;
// Forgot: head.next = null
return newHead;  // List has cycle!

// ✓ CORRECT - Break old link
head.next.next = head;
head.next = null;  // Critical!
return newHead;

Mistake 4: Not handling empty list

// ❌ WRONG - Crashes on null
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    // ... no null check

// ✓ CORRECT - Works for null
// Code naturally handles it!
while (curr != null) {  // Won't enter if head is null
    // ...
}
return prev;  // Returns null for empty list ✓

🎯 Pattern Recognition

Problem Type: Reverse Linked List
Core Pattern: Pointer Reversal

When to Apply:
✓ Need to reverse entire list
✓ Part of larger problem (palindrome, reorder)
✓ Need both directions of traversal

Recognition Keywords:
- "reverse"
- "backward"
- "reverse order"

Similar Problems:
- Palindrome Linked List (LC 234) - Uses reversal
- Reorder List (LC 143) - Uses reversal
- Reverse Nodes in k-Group (LC 25) - Advanced reversal

Key Components:
┌────────────────────────────────────────────┐
│ Three Pointers: prev, curr, next          │
│ Critical: Save before changing!           │
│ Return: prev (new head)                   │
│ Time: O(n), Space: O(1) iterative        │
│ Time: O(n), Space: O(n) recursive        │
└────────────────────────────────────────────┘

🧠 Interview Strategy

Step 1: "I see this is a reversal problem"
Step 2: "I can solve it iteratively or recursively"
Step 3: "Iterative is more space-efficient - I'll use that"
Step 4: "I need three pointers: prev, curr, and next"
Step 5: "Critical: save next before changing pointers"

Key Points to Mention:
- Both iterative and recursive solutions exist
- Iterative is O(1) space, recursive is O(n)
- Must save next pointer before reversing
- prev becomes new head at end
- Works naturally for empty list
- Time: O(n), Space: O(1) or O(n)

Walk Through Example:
"For [1,2,3], I start with prev=null and curr=1.
 At each step, I save next, reverse curr's pointer to prev,
 then move both pointers forward. When curr becomes null,
 prev points to 3, which is the new head."

Edge Cases to Mention:
✓ Empty list → returns null
✓ Single node → returns same node
✓ Two nodes → swap them
✓ Long list → works same way

📝 Quick Revision Notes

🎯 Core Concept:

Reverse Linked List: Use three pointers (prev, curr, next). For each node: save next, reverse pointer to prev, move forward. CRITICAL: save before change! Return prev (new head). Iterative: O(1) space. Recursive: O(n) stack.

⚡ Quick Implementation (Iterative):

import java.util.Arrays;
import java.util.List;

class ListNode {
  int val;
  ListNode next;
  ListNode() {}
  ListNode(int val) { this.val = val; }
  ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
  public static ListNode create(List<Integer> list) {
    ListNode dummy = new ListNode();
    ListNode curr = dummy;

    for(int num : list) {
      curr.next = new ListNode(num);
      curr = curr.next;
    }

    return dummy.next;
  }

  public static void print(ListNode head) {
    ListNode curr = head;
    while (curr != null) {
      System.out.print(curr.val + " -> ");
      curr = curr.next;
    }

    System.out.println();
  }

  public ListNode reverseList(ListNode head) {
    ListNode curr = head;
    ListNode next = null;
    ListNode prev = null;

    while (curr != null) {
      next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }

    return prev;
  }

  public static void main(String[] args) {
    Solution t = new Solution();

    ListNode head1 = create(Arrays.asList(1, 2, 3, 4, 5));
    print(t.reverseList(head1));

    print(t.reverseList(create(Arrays.asList()))); // empty list
    print(t.reverseList(create(Arrays.asList(1)))); // single element
    print(t.reverseList(create(Arrays.asList(1, 2)))); // 2 elements
    print(t.reverseList(create(Arrays.asList(1, 2, 3)))); // odd count
    print(t.reverseList(create(Arrays.asList(1, 2, 3, 4)))); // even count
  }
}

⚡ Quick Implementation (Recursive):

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;

    ListNode newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;

    return newHead;
}

🔑 Key Insights:

Pattern: Pointer reversal
Three pointers: prev, curr, next
CRITICAL: Save next BEFORE changing curr.next!
Return: prev (not curr - it's null!)
Iterative: O(n) time, O(1) space ✓
Recursive: O(n) time, O(n) space

🎪 Memory Aid:

"Save before change, move to next, prev wins!"
Think: "Next → Reverse → Move → Move!" ✨

⚠️ Critical Rule:

The order matters!

1. Save: next = curr.next
2. Reverse: curr.next = prev
3. Move prev: prev = curr
4. Move curr: curr = next

Skip step 1? Lost!

🧪 Edge Cases

Case 1: Empty list

Input: head = null
Output: null

Case 2: Single node

Input: head = [1]
Output: [1]

Case 3: Two nodes

Input: head = [1,2]
Output: [2,1]

Case 4: Multiple nodes

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

All handled correctly by both approaches! ✓

Palindrome Linked List (LC 234) - Uses reversal
Reorder List (LC 143) - Uses reversal
Reverse Nodes in k-Group (LC 25) - Advanced reversal
Reverse Linked List II (LC 92) - Partial reversal

Happy practicing! 🎯

Note: This is THE most fundamental linked list problem! Master both iterative and recursive approaches. The iterative solution appears in 40% of linked list problems as a building block. The pattern of "save before change" is critical for all pointer manipulation problems! 💪✨

90. Reverse Linked List

Problem Statement

🌟 ELI5: The Simple Idea!

🎨 Visual Understanding

The Reversal Process

🎯 Approach 1: Iterative (Recommended) ⭐

The Most Common Interview Solution

Implementation

🔍 Super Detailed Dry Run

🎯 Approach 2: Recursive (Elegant) ⭐

The Elegant Solution

Implementation

🔍 Recursive Dry Run

🎯 Comparison of Approaches

⚠️ Common Mistakes to Avoid

🎯 Pattern Recognition

🧠 Interview Strategy

📝 Quick Revision Notes

🧪 Edge Cases

Related Patterns