Linked lists are one of the most fundamental data structures, and detecting cycles is a classic interview problem. In this post, we’ll solve LeetCode 141 - Linked List Cycle using an elegant two-pointer technique known as Floyd’s Tortoise and Hare Algorithm.

Problem Statement

Given the head of a singly linked list, determine whether the linked list contains a cycle.

A cycle exists if, by following the next pointers, you can visit the same node more than once.

Example 1

Input:
1 → 2 → 3 → 4
    ↑       ↓
    └───────┘

Output: true

The tail connects back to the second node, creating a loop.

Example 2

Input:
1 → 2 → null

Output: false

The list ends normally, so there is no cycle.

---

Intuition

The brute-force idea would be to keep track of every visited node using a set.

If we ever encounter a node we’ve already visited, we’ve found a cycle.

While this approach works, it requires O(n) extra space.

Can we solve it using constant space?

Yes!

---

Floyd’s Tortoise and Hare Algorithm

The key idea is to use two pointers moving at different speeds.

• Slow pointer moves one step at a time.
• Fast pointer moves two steps at a time.

Why does this work?

There are two possible scenarios:

Case 1: No Cycle

The fast pointer eventually reaches the end of the linked list (None).

1 → 2 → 3 → 4 → null

Slow: moves one node at a time
Fast: moves two nodes at a time

Fast reaches null → No cycle

Case 2: Cycle Exists

Once both pointers enter the cycle, the fast pointer gains one node on the slow pointer during each iteration.

Eventually, the fast pointer catches up with the slow pointer.

        ┌──────────┐
        ↓          │
1 → 2 → 3 → 4 → 5
        ↑          │
        └──────────┘

Slow: 1 step
Fast: 2 steps

Eventually:
Slow == Fast

If the two pointers ever point to the same node, we know there’s a cycle.

---

Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head

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

            if slow == fast:
                return True

        return False

---

Step-by-Step Dry Run

Consider the following linked list:

1 → 2 → 3 → 4
    ↑       ↓
    └───────┘

Initially:

Slow = 1
Fast = 1

Iteration 1

Slow → 2
Fast → 3

Iteration 2

Slow → 3
Fast → 2

Iteration 3

Slow → 4
Fast → 4

Both pointers meet!

Return:

True

---

Why Does the Fast Pointer Always Catch the Slow Pointer?

Think of two runners on a circular track.

• One runner moves one step at a time.
• The other moves two steps at a time.

Since they’re running on the same loop, the faster runner keeps gaining ground on the slower one. Eventually, it completes the gap and catches up.

The same logic applies inside a linked list cycle.

---

Complexity Analysis

Operation	Complexity
Time	O(n)
Space	O(1)

• Each pointer traverses the list at most once.
• No additional data structures are used.

This makes Floyd’s algorithm both time-efficient and space-efficient.

---

Key Takeaways

• Use two pointers moving at different speeds.
• If the fast pointer reaches None, there is no cycle.
• If the slow and fast pointers meet, a cycle exists.
• Floyd’s Tortoise and Hare algorithm solves the problem in O(n) time and O(1) space, making it the optimal solution.

This is one of the most frequently asked linked list interview problems, and understanding the intuition behind the two-pointer approach will help you tackle many other linked list questions as well.