This week I decided to study a coding pattern called Fast & Slow Pointers.

According to Philip Wilkinson, a Linked List is a type of data structure that acts as a linear collection of nodes, and each node contains some information and a link or reference to another node. It was time for me to refresh my memory of Linked Lists, and googling Fast & Slow Pointers brings up a lot of results for looking at Linked Lists. One of the common problems used for solving Fast & Slow Pointers involves detecting a cycle in a Linked List. So I headed to leetcode and took a crack at this ‘easy’ rated Linked List problem:

https://leetcode.com/problems/linked-list-cycle/

According to the leetcode prompt, a linked list cycle occurs when a node in the linked list can be reached again by following the pointers to the next node.

As an example of what that might look like, this image is taken from the leetcode prompt (https://leetcode.com/problems/linked-list-cycle/):

Here is the prompt from the leetcode question:

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Source: https://leetcode.com/problems/linked-list-cycle/

On the leetcode site within the question page, it also starts out with some helpful bit at the top inside where you write your code, and it looks like this:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
Source: https://leetcode.com/problems/linked-list-cycle/

It took me a second to refresh my memory on this. I think LL is one of those things that once you understand the basic pattern, it’s easier to jump right into many of these kinds of problems, but coming back to it after a long time, it kind of feels like you need to look at the details again to understand the basics.

So basically what this is showing us in the prompt is that we have a class called ListNode, and it’s a constructor. We have a head node containing ‘x’, and the Linked List only has one node in it, and nothing else, so it points to nothing. Something akin to this:

(head)

(x) -> None

So in the prompt, we can imagine that we have a pointer at the head of the LL, and it contains a head node with element ‘x’, and we can access that head (x) directly, but we have no other nodes in it right now besides this one, so therefore it points to nothing.

The next part of the prompt on the leetcode website gives us this:

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
Source: https://leetcode.com/problems/linked-list-cycle/

So in our solution code, we want to pass in the head of the list (where we had ‘x’ from our previous example).

This isn’t my first go with Linked List struggles, as you can see below the date I (struggled with) I mean solved this problem before:

Source: https://leetcode.com/problems/linked-list-cycle/

At a first glance, I’ll be honest I don’t remember how to solve it from back then from memory, which is honestly good. But I want to think about it for some time and see if I can come up with an answer now using what I know about pointers, and in particular fast and slow pointers.

I tried looking up resources for using fast & slow pointers with Linked List, and some of them referenced this problem. But I didn’t want to see the code to solve it in their articles. I just wanted to see how to approach a problem with Fast & Slow pointers – maybe written in plain English instead of code at most. So I immediately clicked away.

If I could see it written out in English (maybe the solution is written at the bottom and I just avoid looking at it) and I work on converting it to code without seeing the author’s solution yet, that would at least be a learning experience for me. I like this article written by Emre Bolat, which does exactly that: https://emre.me/coding-patterns/fast-slow-pointers/ For now, I didn’t scroll all the way down past his explanation about the Tortoise and Hare (around the first 1/3 of the page). But I like his explanation and animation explanation a lot, plus he uses little turtle and rabbit emojis. He references the same exact problem that I’m looking at. To sum up what Emre Bolat says, here is how to think about this kind of problem, and how one might use Fast & Slow Pointers:

• Iterate over the Linked List
• Create two pointers
• The slow pointer moves one space forward
• The fast pointer moves two spaces forward
• If the fast pointer reaches the end of the Linked List, and doesn't meet with the slow pointer, there is no cycle in the Linked List
• If the fast pointer and slow pointer meet, then there's a cycle in the Linked List
Source: https://emre.me/coding-patterns/fast-slow-pointers/

This is a little loosely like pseudo-code, but it needs to be translated into code.

First, how do we iterate over a linked list? We could start at the head of the Linked List, and we can go from node to node until we find that the reference to the next possible node is None. We could use an infinite loop, and loop forever until we find that the next reference is None, and break out of our loop. Maybe something like this:

cur = head

while True:
    if cur.next is None:
        break
    cur = cur.next

Secondly, how do we implement our fast and slow pointers?

We need to start them both at the head of the list, and then iterate them with the slow pointer moving forward one node at a time, and the fast pointer moving forward two nodes at a time.

Maybe something like this:

slow = head
fast = head

while slow is not None and fast is not None:
    fast = fast.next.next
    slow = slow.next

But we probably have to check that our linked list is not empty. Maybe something like this:

slow = head
fast = head

if head is not None:
    while slow is not None and fast is not None:
        fast = fast.next.next
        slow = slow.next

And we need the condition that checks, do our fast and slow pointers meet? If they meet, we have a cycle. If they don’t ever meet and we exhausted our Linked List, we don’t have a cycle.

slow = head
fast = head

if head is not None:
    while slow is not None and fast is not None:
        fast = fast.next.next
        slow = slow.next
        if fast == slow:
            return True
return False

We might be close here. But after running this against the three example test cases, it looks like I’m missing something in the case that there’s only one node in the list and no cycle. I need logic that checks if the Linked List only has one node, and no cycle.

slow = head
fast = head

if head == None or head.next == None:
    return False
while slow is not None and fast is not None:
    fast = fast.next.next
    slow = slow.next
    if fast == slow:
        return True
return False

There’s another issue with my logic here, in this particular line:

while slow is not None and fast is not None:

We have to check that wherever fast is moving forward to is not None, because if it is, we reached the end of the Linked List and we didn’t detect a cycle. We also don’t really need this bit about slow not being None because slow is always behind. For other problems, we might need to know about slow, but for this particular case, we don’t really need slow because we really care about iterating over the whole list, and fast will do that.

slow = head
fast = head

if head == None or head.next == None:
    return False
while fast is not None and fast.next is not None:
    fast = fast.next.next
    slow = slow.next
    if fast == slow:
        return True
return False

And that’s a wrap.

Here’s a comparison of my solution from 2021 and my solution from 2022:

Sources:

Bolat, Emre. “Coding Patterns: Fast & Slow Pointers.” Emre.me, 22 Oct. 2019, https://emre.me/coding-patterns/fast-slow-pointers/. Accessed 23 Oct. 2022.

“Linked List Cycle” LeetCode, https://leetcode.com/problems/linked-list-cycle/. Accessed 23 Oct. 2022.

Wilkinson, Philip. “A Complete Guide to Linked Lists in Python.” Medium, Towards Data Science, 1 Oct. 2022, https://towardsdatascience.com/a-complete-guide-to-linked-lists-in-python-c52b6cb005. Accessed 23 Oct. 2022.