Iterative In-Place Linked List Reversal

1. Understanding the Problem: Reversing the Links

First, let's define the problem. A singly linked list is a chain of nodes, where each node contains some data and a pointer to the next node in the sequence. The entire list is identified by a single pointer to the first node, the head.

Given a head pointer, our task is to reverse the list. This does not mean swapping the data values within the nodes. Instead, we must re-wire the next pointers of each node to point to its previous node. The key constraint is to do this in-place, meaning we should not allocate any new nodes and should only use a constant amount of extra memory (a few pointer variables), which is an O(1) space complexity.

Let's watch a short video that clearly visualizes this goal.

As you saw, the original list 1 -> 2 -> 3 -> NULL becomes 3 -> 2 -> 1 -> NULL, and the head pointer is updated to point to the new first node, which was the original last node.

2. The Iterative Algorithm: The Three-Pointer Technique

The core challenge is this: as we traverse the list, if we change current_node->next to point to the previous node, we lose the link to the rest of the list. How can we advance to the next node after we've broken the forward link?

The solution is to use three pointers to keep track of our position as we iterate through the list. Let's call them previous, current, and next.

• current: The node we are currently visiting. We start with current = head.
• previous: The node that came before current. For the very first node, its new next pointer should be NULL, so we initialize previous = NULL.
• next: A temporary pointer to store the address of the node that comes after current. This is the key to not losing our place.

The algorithm proceeds in a loop until we have processed the entire list (current becomes NULL):

1. Save the next node: Before we change any pointers, we must save our link to the rest of the list: next = current->next;
2. Reverse the link: Now we can safely rewire the current node's pointer to point backwards: current->next = previous;
3. Advance the pointers: We're done with the current node. For the next iteration, the current node becomes the previous node, and the node we saved in next becomes the new current node.
   • previous = current;
   • current = next;

Once the loop finishes, current will be NULL, and previous will be pointing to what was the last node of the original list—the new head.

Let's see this logic explained with a step-by-step walkthrough.

3. C Implementation and Code Walkthrough

Now that we have the algorithm, let's look at a clean implementation in C. The function will take the current head as an argument and return the new head of the reversed list.

Here is the core logic from that resource, which you should now be able to understand fully:

struct Node* reverseList(struct Node* head) {
    // Initialize pointers
    struct Node *curr = head;
    struct Node *prev = NULL;
    struct Node *next = NULL;

    // Traverse the list
    while (curr != NULL) {
        // 1. Store the next node
        next = curr->next;

        // 2. Reverse the current node's pointer
        curr->next = prev;

        // 3. Move pointers one position ahead
        prev = curr;
        curr = next;
    }

    // The new head is the last node we processed
    head = prev;
    return head;
}

4. Edge Cases and Complexity

In any algorithm, especially in an interview setting, you must consider the edge cases.

• Empty List: If head is NULL, curr starts as NULL. The while loop condition (curr != NULL) is immediately false. The function returns prev, which was initialized to NULL. This is the correct behavior.
• Single-Node List: If the list is 10 -> NULL, curr is Node(10). The loop runs once.
  1. next becomes curr->next, which is NULL.
  2. curr->next becomes prev, which is NULL. (The list is now 10 -> NULL, which is what we want).
  3. prev becomes curr (Node(10)).
  4. curr becomes next (NULL).
     The loop terminates. The function returns prev (Node(10)), which is correct.

The implementation is robust. Let's confirm this by watching the final segment of the video, which demonstrates the code running against these cases.

Complexity Analysis

• Time Complexity: O(n). We must visit every node in the list exactly once to reverse its pointer. The amount of work is directly proportional to the number of nodes, n.
• Space Complexity: O(1). We only use a fixed number of extra pointer variables (prev, curr, next) regardless of the list's size. This is constant space and satisfies the "in-place" requirement, a crucial detail for memory-constrained environments like those you work in.

Conclusion

You have now mastered the iterative, in-place algorithm for reversing a linked list. This problem is a perfect microcosm of advanced C programming: it requires precise pointer manipulation, careful state management, and a solid understanding of memory layout.

Key Takeaways:

• Reversing a linked list in-place means re-wiring the next pointers, not moving data.
• The iterative solution hinges on the three-pointer technique (previous, current, next).
• The most critical step is saving current->next to a temporary next pointer before you overwrite it.
• The algorithm correctly handles edge cases like empty and single-node lists.
• The solution has an optimal time complexity of O(n) and space complexity of O(1).

Preview of the Next Lesson

Having sharpened our skills with one classic pointer problem, we'll move to another. In the next lesson, we will solve the linked list cycle detection problem using Floyd's Tortoise and Hare algorithm. This is another famous interview question that uses a clever two-pointer technique to solve a seemingly complex problem with elegance and efficiency.