LeetCode Solution 206 - Reverse a Linked List

Problem Statement

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

Constraints:

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

Optimal Approach

The most efficient way to solve this problem is using Iterative In-Place Reversal:

1. Traverse the list while maintaining three pointers: prev, curr, and next.
2. Reverse the direction of the next pointer at each step.
3. Return the new head of the reversed list.

LeetCode-Compatible C++ Solution (Iterative Approach)

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

Step-by-Step Explanation of Code

1. Initialize prev to nullptr and curr to head.
2. Iterate through the list:
   • Store next = curr->next (to avoid losing reference to the next node).
   • Reverse curr->next to point to prev.
   • Move prev and curr one step forward.
3. Return prev as the new head (since curr becomes nullptr at the end).

Dry Run / Execution Steps

Example Input:

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

Execution Steps:

Initial:   1 → 2 → 3 → 4 → 5 → nullptr
Step 1:    nullptr ← 1   2 → 3 → 4 → 5
Step 2:    nullptr ← 1 ← 2   3 → 4 → 5
Step 3:    nullptr ← 1 ← 2 ← 3   4 → 5
Step 4:    nullptr ← 1 ← 2 ← 3 ← 4   5
Step 5:    nullptr ← 1 ← 2 ← 3 ← 4 ← 5 (New head = 5)

Output:

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

Alternative Approaches

1. Recursive Approach

• Recursively reverse the rest of the list and update links.
• Time Complexity: O(N)
• Space Complexity: O(N) (due to recursive call stack)
• Why not? Uses extra space due to recursion depth.

2. Stack-Based Approach

• Store nodes in a stack and reconstruct the list.
• Time Complexity: O(N)
• Space Complexity: O(N)
• Why not? Uses extra memory.

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Feasibility
Iterative	O(N)	O(1)	✅ Best Choice
Recursive	O(N)	O(N)	❌ Extra stack usage
Stack-Based	O(N)	O(N)	❌ Extra memory

Conclusion

The Iterative In-Place Approach is the best method as it provides O(N) time complexity with O(1) space complexity.

Similar Problems for Practice

• Reverse Linked List II (LeetCode 92)
• Palindrome Linked List (LeetCode 234)
• Rotate List (LeetCode 61)