Finding the Middle of a Linked List

1. Understanding the "Middle"

First, let's clearly define the problem. Finding the middle of a list with an odd number of nodes is straightforward. For a list like 1 -> 2 -> 3 -> 4 -> 5, the middle node is 3.

But what about a list with an even number of nodes, like 1 -> 2 -> 3 -> 4 -> 5 -> 6? There are two "middle" nodes, 3 and 4. In such cases, the standard convention for this problem (as seen on platforms like LeetCode) is to return the second middle node. So, for the even-length list, the answer would be 4.

The following video from the 'take U forward' channel provides a quick, clear explanation of this problem definition.

2. The Naive Approach: A Two-Pass Solution

Before jumping to the optimal solution, let's consider the most intuitive way to solve this. If you knew the total number of nodes in the list, you could easily find the middle.

This leads to a simple two-pass algorithm:

1. First Pass: Traverse the entire linked list from head to null just to count the total number of nodes, let's call it N.
2. Second Pass: Calculate the index of the middle node. Based on the problem's rule, this would be the (N/2) + 1-th node. Reset a pointer to the head and traverse (N/2) times to reach this middle node.

This approach works correctly.

• Time Complexity: You traverse the list once fully and then about half-way again, giving a complexity of O(N + N/2), which simplifies to O(N).
• Space Complexity: You only use a few variables for counting and traversal, so the space is O(1).

While the complexity is linear, a common follow-up question in an interview is, "Can you do this in a single pass?" Let's see how.

3. The Optimal Solution: The Slow and Fast Pointer Technique

This is where the technique from our previous lesson shines. The intuition is beautifully simple:

If you have two pointers, one moving twice as fast as the other, by the time the fast pointer reaches the end of the list, the slow pointer will have traveled exactly half the distance. This means the slow pointer will be positioned at the middle element.

Let's apply this:

• Initialize two pointers, slow and fast, both pointing to the head.
• In each step of a loop, move slow one node forward (slow = slow.next) and fast two nodes forward (fast = fast.next.next).
• The loop continues as long as fast and its next node are not null.

Let's trace this with the image below.

Let's see how this handles our two cases:

• Odd Length List (e.g., 5 nodes): The fast pointer will land on the last node. It cannot move further because fast.next is null. At this exact moment, the slow pointer will be at the middle node.
• Even Length List (e.g., 6 nodes): The fast pointer will completely traverse the list and become null. The loop terminates, and the slow pointer will be at the second of the two middle nodes, which is exactly what the problem requires.

This video provides a detailed walkthrough of this algorithm, showing how the pointers move for both odd and even length lists.

4. Java Implementation

The implementation in Java is concise and directly follows the logic we've discussed. The most important part is the while loop's condition, which elegantly handles both odd and even length lists.

Here is the core Java code for the algorithm:

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

public class Solution {
    public ListNode findMiddle(ListNode head) {
        // If list is empty or has only one node, head is the middle
        if (head == null || head.next == null) {
            return head;
        }

        ListNode slow = head;
        ListNode fast = head;

        // The loop condition is crucial
        // 1. fast != null: Handles even-length lists.
        // 2. fast.next != null: Handles odd-length lists.
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // When the loop ends, slow is at the middle
        return slow;
    }
}

Complexity Analysis

• Time Complexity: O(N). The fast pointer traverses the list once, so the loop runs for approximately N/2 iterations. This gives us linear time complexity. Crucially, it's done in a single pass.
• Space Complexity: O(1). We only use two node pointers, slow and fast, providing a constant space solution.

Conclusion

Great job! You've successfully adapted the slow and fast pointer technique to a new problem, reinforcing this powerful pattern. This approach is highly valued in interviews because it's efficient, elegant, and demonstrates a solid grasp of pointer manipulation.

Key Takeaways:

• Reusability: The slow/fast pointer technique is not just for cycle detection; it's a versatile pattern for linked list problems.
• The Core Logic: The fundamental idea is that the slow pointer covers half the distance of the fast pointer. By the time the fast pointer finishes its traversal, the slow pointer is naturally at the halfway point.
• Efficiency: This single-pass, O(1) space algorithm is the optimal solution for finding the middle element.

Preview of the next lesson:
We will continue exploring clever pointer manipulations. In the next lesson, you will learn how to find the intersection point of two linked lists. This problem introduces another non-obvious but highly efficient pointer-based solution that will further expand your problem-solving toolkit.