Reversing a Linked List

1. The Problem: Reversing the Links

Let's be clear about the task. If you are given the head of a list like this:
1 -> 2 -> 3 -> 4 -> NULL

Your function should modify the pointers to create this structure:
4 -> 3 -> 2 -> 1 -> NULL

And, importantly, your function must return the new head of the list, which in this case is the node containing 4.

2. The Iterative Approach: Juggling Pointers

The most common and space-efficient way to solve this problem is iteratively. The core idea is to traverse the list, and for each node we visit, we'll reverse its next pointer to point to the node that came before it.

To do this without losing track of the rest of the list, we need to manage three pointers at each step:

1. previous: The node that came before the current one. It starts as null because nothing comes before the head.
2. current: The node we are currently processing. It starts at the head.
3. next: A temporary pointer to store the next node in the original list before we overwrite current.next.

The algorithm proceeds as follows, looping until current becomes null:

1. Save the next node: next = current.next;
2. Reverse the pointer: current.next = previous;
3. Move pointers forward: previous = current; and current = next;

Once the loop finishes, previous will be pointing to the original tail of the list, which is our new head.

To see this logic animated step-by-step, the following video provides an exceptionally clear walkthrough. Pay close attention to how the three pointers (previous, current, and front/next) interact in each iteration.

Java Implementation (Iterative)

Here is a clean Java implementation of the iterative approach.

The core logic from the article looks like this:

// Assuming a ListNode class is defined:
// class ListNode {
//     int val;
//     ListNode next;
//     ListNode(int x) { val = x; }
// }

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

    while (current != null) {
        // Store the next node before we change the pointer
        next = current.next;
        
        // Reverse the current node's pointer
        current.next = prev;
        
        // Move prev and current one step forward
        prev = current;
        current = next;
    }
    
    // At the end, prev will be the new head
    return prev;
}

• Time Complexity: O(N) because we visit each node exactly once.
• Space Complexity: O(1) because we only use a few extra pointers, regardless of the list's size. This is the optimal solution and the one you should aim for in an interview.

3. The Recursive Approach: Divide and Conquer

The recursive solution is elegant but can be harder to grasp initially. It's a great exercise for strengthening your recursion skills. The main idea is to think of the problem in terms of a smaller, already solved subproblem.

Logic:

1. Base Case: If the list is empty (head == null) or has only one node (head.next == null), it's already reversed. So, we just return the head.
2. Recursive Step:
   • Assume we can magically reverse the rest of the list (from head.next onwards). We call reverseList(head.next).
   • This recursive call returns the newHead of the reversed sub-list.
   • Now, we need to attach the original head to the end of this reversed sub-list.
     • head.next still points to the original next node, which is now the tail of the reversed sub-list.
     • So, we set head.next.next = head; to make that tail node point back to our current head.
     • Finally, we must break the original forward link to avoid a cycle: head.next = null;.
   • We return the newHead that we received from the recursive call, as it is the head of the entire reversed list.

This process can feel like magic. The following video does a phenomenal job of demystifying it by walking through the call stack and showing how the pointers are re-linked as the recursion unwinds.

Java Implementation (Recursive)

Here is the corresponding Java code for the recursive method.

The recursive function is remarkably concise:

public ListNode reverseList(ListNode head) {
    // Base case: empty list or list with only one node
    if (head == null || head.next == null) {
        return head;
    }
    
    // Recursively reverse the rest of the list
    ListNode newHead = reverseList(head.next);
    
    // Reverse the pointers for the current node
    head.next.next = head;
    head.next = null;
    
    // Return the new head (which is passed up from the base case)
    return newHead;
}

• Time Complexity: O(N), as each node is visited once during the recursive calls.
• Space Complexity: O(N), due to the depth of the recursion call stack. In the worst case, a list of size N will lead to N nested function calls before the base case is reached.

Conclusion

Congratulations! You've just learned two powerful ways to reverse a linked list, a problem that is a staple of coding interviews.

Key Takeaways:

• Iterative Reversal: Uses three pointers (previous, current, next) to reverse the links in a single pass. It's the most efficient solution with O(N) time and O(1) space complexity. This is the standard expected answer in most interviews.
• Recursive Reversal: Solves the problem by breaking it down: reverse the tail of the list, then attach the head to the end. It's an elegant solution with O(N) time and O(N) space complexity (due to the call stack).

Understanding both approaches demonstrates a deep command of pointer manipulation and recursion.

Preview of the next lesson:
We will continue exploring classic linked list problems. Next, we will tackle another interview favorite: detecting a cycle in a linked list. You'll learn a clever and efficient pointer-based technique known as Floyd's Tortoise and Hare algorithm.