Algorithm-Day23-Reverse-Linked-List-lc-206

Posted on In , Views:

🧩 Problem Description

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

Example:

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

💡 Brute Force (Not In-Place)

  • Store values in an array or stack, then rebuild the list.
  • ❌ Not optimal — uses extra space.

💡 Optimal Approach: Iterative In-Place Reversal

✨ Key Idea

  • Use 3 pointers:
    • prev to track the previous node.
    • curr as the current node.
    • next to temporarily hold curr.next.

At each step:

  • Reverse the link: curr.next = prev
  • Move forward

🔢 Java Code (Iterative)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

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

        return prev;
    }
}

🔁 Java Code (Recursive)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

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

        return reversed;
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n)
  • Space Complexity:
    • Iterative: O(1)
    • Recursive: O(n) (due to recursion stack)

✍️ Summary

  • This is a fundamental linked list pattern — useful in many real problems (e.g., palindrome check, list reordering).
  • Understand both iterative and recursive versions.

Learn it well — this reversal logic appears often in interviews and linked list puzzles.