1. Understanding the Problem

You are given the head of a singly linked list. Your task is to reverse the direction of all the pointers in the list, and then return the new head of the reversed list.

For example, if your list is 1 -> 2 -> 3 -> null, your function should transform it into 3 -> 2 -> 1 -> null, and return the node containing 3.

The Core Constraint (The Trap):

In a singly linked list, each node only knows about the node immediately after it. If you change a node's next pointer to point backwards without first saving where it originally pointed, you instantly sever your connection to the rest of the list. It becomes "orphaned" in memory, completely unreachable. You must carefully choreograph your pointer movements to avoid dropping the rest of your data.

2. The Naive Approach: The Stack or Array Transfer

The most intuitive way to solve this without worrying about delicate pointer surgery is to use extra memory. You can traverse the original list and push every node's value into an Array or a Stack. Once you reach the end, you pop the values out (which naturally reverses their order) and build a brand-new linked list from scratch.

Trade-off Analysis

While this logic is valid and will pass basic test cases, it is highly inefficient for production environments:

• Time Complexity: O(N) — You have to iterate through the list twice (once to read, once to rebuild).
• Space Complexity: O(N) — You are allocating extra memory to store every single value in a new data structure. In a systems programming interview, failing to do this "in-place" is a major red flag.

3. The Optimal Approach: In-Place Reversal (O(1) Space)

To pass a senior-level technical interview, we want to achieve an O(1) space complexity. We must reverse the list in-place, meaning we simply rewire the existing arrows without creating any new nodes or using auxiliary data structures.

Imagine you are walking down a trail leaving a rope behind you. To reverse your path, you need to turn around and pull the rope back the way you came. To do this without getting lost, you need to keep track of three things at all times: where you just were (Previous), where you are right now (Current), and where you were about to step next (Next).

4. The Logic Step-by-Step

1. Initialize Pointers:
   • Set a prev pointer to null. This will eventually become the end of our reversed list.
   • Set a curr pointer to the head of the list.
2. Traverse and Rewire: Create a loop that continues as long as curr is not null.
   • Save the Future: Before you change any arrows, save the next node in a temporary variable: next_node = curr.next. (If you skip this, you lose the rest of the list!)
   • Reverse the Arrow: Point the current node backwards by setting curr.next = prev.
   • Shift Pointers Forward: Move prev forward to where curr is: prev = curr.
   • Move curr forward to where next_node is: curr = next_node.
3. When the loop breaks, curr has fallen off the edge (it is null). The prev pointer is safely resting on the very last node of the original list, which is the new head. Return prev.

5. Complexity Analysis

• Time Complexity: O(N) — We traverse the linked list exactly once, touching each node one time to reverse its pointer.
• Space Complexity: O(1) — We only use three temporary pointers (prev, curr, next_node) regardless of how massively long the linked list is. We have successfully achieved constant space!

6. Code Implementations

Expand the sections below to see the optimal O(1) space "Three-Pointer" implementations across different languages.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseList(self, head) -> ListNode:
        prev = None
        curr = head
        
        while curr:
            # 1. Save the next node
            next_node = curr.next
            
            # 2. Reverse the arrow
            curr.next = prev
            
            # 3. Shift pointers forward
            prev = curr
            curr = next_node
            
        # prev is now pointing to the new head
        return prev

/**
 * Definition for singly-linked list.
 * public 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 ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            // 1. Save the next node
            ListNode nextNode = curr.next;
            
            // 2. Reverse the arrow
            curr.next = prev;
            
            // 3. Shift pointers forward
            prev = curr;
            curr = nextNode;
        }
        
        // prev is now pointing to the new head
        return prev;
    }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        
        while (curr != nullptr) {
            // 1. Save the next node
            ListNode* nextNode = curr->next;
            
            // 2. Reverse the arrow
            curr->next = prev;
            
            // 3. Shift pointers forward
            prev = curr;
            curr = nextNode;
        }
        
        // prev is now pointing to the new head
        return prev;
    }
};

7. Conclusion: You Are Ready

Congratulations, you have just mastered one of the most famous algorithms in computer science history. The "Iterative In-Place Reversal" teaches you a critical lesson: when modifying a data structure, always secure your path forward before you sever the bridge behind you. Keep this three-pointer shuffle deeply ingrained in your memory. You will need to reuse this exact logic as a helper function for advanced interview problems, such as reversing a linked list in k-groups, checking if a list is a palindrome, or reordering a list!