Crushing Tech Interviews with the Fast and Slow Pointer Pattern

This is quite a nifty pattern to apply to linked lists (also arrays and other sequences).

Also known as:

• Hare and Tortoise algorithm.
• Floyd's algorithm.

The pattern is famously used for cycle detection but can be used to solve other sorts of problems too. This is such a good example of a simple but very effective algorithm.

By moving two pointers at different speeds, the algorithm proves that the two pointers are bound to meet. Here's a great StackOverflow post on the proof behind the algorithm: https://cs.stackexchange.com/a/45540

So, let's solve the following question:

Given the head of a singly-linked list, how would you go about determining whether there is a cycle in it or not?

Cast your mind back to the old fable of the tortoise and the hare. Imagine them both on the track (In our case, the linked list). Now, we know that if the track is circular, then the faster hare will be able to eventually catch up and lap the tortoise from behind eventually. This is the same concept behind the tortoise and hare algorithm.

We traverse the linked list with a slow and fast pointer. At each iteration of the traversal, the slower pointer moves one element forward and the fast pointer moves two elements forward. If there's a cycle, they are eventually going to meet.

So what happens if there isn't a cycle in the linked list? Well, in that case the fast pointer will reach the tail of the linked list and hit a null value (indicating the tail) and we will conclude that the linked list doesn't have a cycle.

Pretty nifty eh?

Here's a visual representation to get your head around it:

And here's some python code:

def has_cycle(head: LinkedListNode):
    slow, fast = head, head

    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next

        if slow == fast:
            return True

    return False

And that's it! Like I said before: Simple yet effective.

Some extra questions for you to have a go at:

https://leetcode.com/problems/middle-of-the-linked-list/ (Easy)

https://leetcode.com/problems/happy-number/ (Easy)

https://leetcode.com/problems/linked-list-cycle-ii/ (Medium)

If you enjoyed this article, please go support the people over at educative.io/courses/grokking-the-coding-in... I've based this blog post on their content.