Detect a Cycle in a Linked List in Python | Floyd’s Cycle-Finding Algorithm | LeetCode 141

After mastering how to find the middle of a list, the next challenge is identifying if a list is “broken.” In a normal Linked List, you eventually hit None. But in a Cyclic Linked List, the last node points back to a previous node, creating an endless loop.

This is LeetCode Problem 141 – Linked List Cycle. If you’ve ever been stuck in a traffic roundabout with no exit, you already understand the problem. Now, let’s look at the smartest way to solve it in a single pass.

The Mental Model: Two Runners on a Track

Think of a circular racing track. If two people are running at the exact same speed, they will never meet. But if one person (the Hare) runs twice as fast as the other (the Tortoise), the faster runner will eventually “lap” the slower one.

In a Linked List:

• If there is no cycle, the Fast pointer will reach the end (None).

• If there is a cycle, the Fast pointer will eventually catch up to the Slow pointer from behind.

Python Code Implementation

Here is the optimized solution using the Two-Pointer technique.

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # Both racers start at the starting line
        slow = fast = head
        
        # While the Rabbit has a path to run...
        while fast and fast.next:
            slow = slow.next          # Moves 1 step
            fast = fast.next.next     # Moves 2 steps
            
            # The Magic Moment: They meet!
            if slow == fast:
                return True
        
        # If the Rabbit hits a dead end, there's no cycle
        return False

Step-by-Step Dry Run

Let’s look at a list where the last node (4) points back to (2):

1 → 2 → 3 → 4 → (back to 2)

Final Result: True (Cycle Detected).

Key Takeaways for Technical Interviews

• Time Complexity: O(n). Even in a cycle, the Fast pointer will meet the Slow pointer in less than two full laps.

• Space Complexity: O(1). We are only using two pointers regardless of how big the list is.

• Why not use a Hash Set? You could store every visited node in a set and check for duplicates. That is O(n) space. Interviewers prefer the O(1) pointer approach because it’s more memory-efficient.

Watch the Full Video Tutorial

I’ve walked through the logic of Floyd’s Algorithm on my YouTube channel. If you want to see the whiteboard visualization and the code running in real-time, check it out below!

[Watch the Video: Linked List Cycle Explained]

Get the Full Source Code

Want to test this on your local machine? I’ve uploaded the complete Python script, including the ListNode class and a helper function to create cycles for testing.

Access the Code on GitHub

Frequently Asked Questions (FAQs)

1. Will the Fast pointer ever “jump over” the Slow pointer and never meet?

No. Because the relative speed between them is 1 node per step, the distance between them decreases by exactly 1 in every iteration until it becomes 0.

2. What if the cycle is very large?

The algorithm still works! It doesn’t matter where the cycle starts or how big it is; the Fast pointer will always close the gap.

3. What is the next step after detecting a cycle?

The next common interview question is LeetCode 142, where you have to find the exact node where the cycle begins. (Hint: It involves a bit more pointer math!)

Ready for the next challenge? Now that you can find the middle and detect cycles, let’s learn how to DETECT STARTING POINT OF YOUR CYCLE without losing your mind!

Next Problem: [Leetcode #141 : Detect Starting Point of Your Cycle]