Fast and Slow Pointers in Linked Lists

The Fast and Slow Pointer Pattern

The core idea is simple yet elegant. You initialize two pointers, typically named slow and fast, at the head of the linked list. Then, you traverse the list by moving the pointers at different speeds:

• The slow pointer advances one node at a time: slow = slow.next.
• The fast pointer advances two nodes at a time: fast = fast.next.next.

This difference in speed creates a dynamic relationship between the pointers that we can exploit to gather information about the list's structure.

Now, let's put this pattern into practice with our first problem.

Application 1: Finding the Middle of a Linked List

Problem: Given the head of a singly linked list, return the middle node of the list. If the list has an even number of nodes, there are two middle nodes; in this case, return the second one.

A naive approach would be to traverse the list once to count the total number of nodes, N, then traverse it a second time up to N/2 to find the middle node. This works, but it requires two full or partial passes. The fast and slow pointer technique allows us to do it in just one.

The intuition is straightforward: since the fast pointer moves twice as fast as the slow pointer, by the time fast reaches the end of the list, slow will naturally be positioned at the middle.

The following video provides an excellent walkthrough of this logic.

As the video demonstrated, the loop termination condition is key:

• Odd-length list: The fast pointer will end up on the very last node. fast.next will be None, terminating the loop.
• Even-length list: The fast pointer will land on the second-to-last node, and its next jump (fast.next.next) will make it None, terminating the loop.

In both scenarios, the slow pointer will be left at the correct middle node.

Here is a typical Python implementation:

def find_middle(head):
    slow = head
    fast = head




    # The loop continues as long as fast and the node after it are not None.
    # This prevents an error when trying to access fast.next.next.
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    



    # When the loop ends, slow is at the middle.
    return slow

This single-pass solution has a time complexity of $O(N)$ and, crucially, a space complexity of $O(1)$, making it highly efficient.

Application 2: Detecting a Cycle (Floyd's Tortoise and Hare)

Problem: Given the head of a linked list, determine if the list has a cycle in it.

This is a classic interview question. How can you tell if a list loops back on itself? If you simply traverse it, you'll get stuck in an infinite loop.

A good first thought, which you might propose in an interview, is to use a hash set to keep track of visited nodes.

The $O(N)$ space complexity of the hash set method is often a point an interviewer will press on, asking for a more memory-efficient solution. This is where the fast and slow pointer technique shines, providing an $O(1)$ space solution.

The logic is as follows:

1. If there is no cycle, the fast pointer will eventually reach the end of the list (None).
2. If there is a cycle, the fast pointer will enter the cycle and start "lapping" the slow pointer. Because the fast pointer gains one position on the slow pointer with every iteration inside the cycle, they are guaranteed to meet eventually.

The next segment of the NeetCode video gives a brilliant, intuitive proof for why they are guaranteed to meet.

With that intuition, the implementation is surprisingly concise.

Follow-up: Finding the Start of the Cycle

A common follow-up question is: "Great, you've detected a cycle. Now can you find the node where the cycle begins?"

Floyd's algorithm includes a beautiful second phase for this. The proof is based on the distances traveled by the pointers, but the algorithm itself is simple:

1. Use the fast and slow pointers to find the first meeting point within the cycle.
2. Once they meet, reset one pointer (say, slow) back to the head of the list. Leave the other pointer (fast) at the meeting point.
3. Now, advance both pointers one step at a time (slow = slow.next, fast = fast.next).
4. The node where they meet again is the start of the cycle.

This two-phase process is perfectly illustrated in the following diagram.

The code for this extension builds directly on the detection code.

Conclusion

In this lesson, you've added a powerful and efficient pattern to your toolkit. The fast and slow pointer technique is a prime example of the kind of algorithmic thinking that interviewers at top companies look for: identifying an elegant solution that optimizes for space and time.

Key Takeaways:

• The fast and slow pointer technique uses two pointers moving at different speeds to solve problems on sequences, particularly linked lists.
• It provides an $O(1)$ space complexity solution for problems that might otherwise require $O(N)$ space (like using a hash set).
• Finding the middle element: When the fast pointer reaches the end of the list, the slow pointer is at the middle.
• Cycle detection: If the fast and slow pointers ever meet, a cycle exists. They are guaranteed to meet if a cycle is present.
• Finding the cycle's start: After finding a meeting point, reset one pointer to the head and advance both one step at a time. Their next meeting point is the start of the cycle.

In our next lesson, we will tackle another classic linked list problem: merging two sorted lists. This will further hone your pointer manipulation skills and introduce a core component used in famous sorting algorithms.