Finding the Middle Node of a Linked List

Recommended resources

The freely available resources this lesson will direct you to.

Welcome back. In our previous lesson, you mastered the iterative reversal of a linked list, a fundamental operation that requires careful pointer manipulation. We saw how using prev, curr, and next_temp pointers allows us to rewire the list without losing track of the nodes.

Today, we will explore another powerful pointer-based pattern: the fast and slow pointer technique, sometimes called the "Tortoise and Hare" algorithm. Our goal is to apply this pattern to find the middle node of a linked list in a single pass. This is a classic problem that showcases how relative movement of pointers can solve problems that might otherwise seem to require multiple traversals.

The Problem and a Naive Approach

The task is to find the middle node of a singly linked list. If the list has an even number of nodes, there are two middle nodes; in such cases, the standard convention is to return the second one. For example:

1 -> 2 -> 3 -> 4 -> 5 -> The middle is 3.
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> The two middles are 3 and 4. We return 4.

The most direct approach that comes to mind is to perform two passes:

First Pass: Traverse the entire list to count the total number of nodes, let's call it N.
Second Pass: Start from the head again and traverse N / 2 times. The node you land on is the middle node.

This works, but it's inefficient. For a very large list, traversing it twice can be costly. The following video explains this two-pass solution in detail. Understanding this baseline approach helps appreciate the elegance of the single-pass solution we're about to learn.

L13. Find the middle element of the LinkedList | Multiple Approaches

This segment from the take U forward channel thoroughly breaks down the two-pass approach.

Watch the explanation starting from the naive solution. Pay attention to how the length is first calculated and then used in a second traversal to find the middle.

As the video points out, we can do better. The key to a single-pass solution lies in using pointers that move at different speeds.

The Fast and Slow Pointer Intuition

Imagine two runners starting at the same point on a straight track. One runner (the "fast" one) runs at twice the speed of the other (the "slow" one). When the fast runner reaches the end of the track, where will the slow runner be? Exactly at the halfway point.

We can apply this exact same logic to a linked list.

This image illustrates the "Tortoise and Hare" analogy. The faster rabbit moves two nodes for every one node the slower tortoise moves. When the rabbit reaches the end, the tortoise is at the middle.

We'll initialize two pointers, slow and fast, both at the head of the list. Then, we'll iterate, moving them at different rates:

slow advances one node at a time (slow = slow.next).
fast advances two nodes at a time (fast = fast.next.next).

When the fast pointer reaches the end of the list, the slow pointer will be positioned exactly at the middle node.

The following video provides a fantastic animated walkthrough of this process for both odd and even length lists.

Middle of a Linked List (LeetCode 876) | Full Solution with animations | Study Algorithms

This video by Nikhil Lohia uses a great analogy and animations to build intuition for the fast and slow pointer technique.

First, watch the car speed analogy to solidify the core concept of relative speeds. Next, see the algorithm in action with an odd-length list. Notice where slow is when fast reaches the last node. Finally, watch the walkthrough for an even-length list. Observe how the pointers' final positions naturally result in the second middle node being selected.

Algorithm Details and Implementation

The logic seems straightforward, but the implementation requires careful handling of the loop termination condition to avoid null pointer exceptions. Let's look at the structure of the algorithm.

Initialize: slow = head, fast = head.
Iterate: The loop must continue as long as the fast pointer can still make a two-step jump. This means we must check that fast itself is not null and that fast.next is also not null. The condition is while (fast != null && fast.next != null).
Move Pointers: Inside the loop, update the pointers:
- slow = slow.next
- fast = fast.next.next
Return: Once the loop terminates, slow will be pointing at the middle node. Return slow.

The image below shows the step-by-step execution for a list with 5 nodes.

A step-by-step visualization of the fast and slow pointers. In each step, `slow` moves one node forward while `fast` moves two. When `fast` reaches the end, `slow` is at the middle node (value 2).

To solidify your understanding of the implementation, including how it handles odd and even cases so gracefully, the following resource provides an excellent, detailed breakdown.

876. Middle of the Linked List - In-Depth Explanation

This AlgoMonster article provides a rigorous yet intuitive explanation of the algorithm, its mathematical basis, and step-by-step walkthroughs.

First, read the Intuition section for a clear summary of why this works. Next, carefully study the Algorithm Steps. Pay special attention to the while loop condition (while fast and fast.next:). This is the most crucial part of the implementation. Finally, review the detailed Example Walkthroughs for both odd and even length lists to see the pointer movements at each step.

From Logic to Code: Pitfalls and Complexity

As someone preparing for coding interviews, knowing the common pitfalls is as important as knowing the correct algorithm. The fast/slow pointer pattern for finding the middle node is elegant, but small mistakes in the loop condition or pointer update order can lead to bugs.

876. Middle of the Linked List - In-Depth Explanation

This second part of the AlgoMonster article provides code examples and highlights common errors.

First, review the Python solution (or your preferred language) to see the complete implementation. Next, read the analysis of Time and Space Complexity. Unsurprisingly, the time complexity is O(N) as we traverse the list once, and the space complexity is O(1) as we only use two extra pointers. Finally, and most importantly, carefully read the entire Common Pitfalls section. This covers incorrect loop conditions and off-by-one errors, which are exactly the kinds of details that interviewers look for.

Conclusion

In this lesson, you've added the fast and slow pointer technique to your algorithmic toolkit. We saw how this pattern provides a highly efficient, single-pass solution to find the middle node of a linked list, elegantly handling both odd and even length cases without special logic. This is a significant step up from the more naive two-pass approach.

Key Takeaways:

The fast and slow pointer pattern involves two pointers moving through a list at different speeds.
To find the middle node, the fast pointer moves two steps for every one step of the slow pointer.
When fast reaches the end, slow is at the middle.
The loop condition while (fast != null && fast.next != null) is critical for correctly and safely handling both odd and even length lists.
This algorithm runs in $O (N)$ time and $O (1)$ space.

This pattern is not a one-trick pony. In our next lesson, we will see how a slight variation of the fast and slow pointer technique can be used to solve another classic problem: detecting a cycle in a linked list.