LeetCode 141: Linked List Cycle

Problem Restatement

We are given the head of a linked list.

Return True if the linked list contains a cycle.

Otherwise, return False.

A cycle exists if some node can be reached again by continuously following next pointers.

LeetCode internally represents the cycle using an index pos, where the tail node points back to the node at position pos. This value is not passed to the function. (leetcode.com)

Examples

Example 1:

3 -> 2 -> 0 -> -4
     ^         |
     |_________|

The tail points back to the node with value 2.

So the list contains a cycle.

Output:

True

Example 2:

1 -> 2
^    |
|____|

The second node points back to the first node.

Output:

True

Example 3:

1 -> None

There is no cycle.

Output:

False

Input and Output

Function shape:

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

First Thought: Store Visited Nodes

One simple idea is:

1. Walk through the linked list.
2. Store every visited node in a set.
3. If we ever visit the same node again, a cycle exists.

Example:

A -> B -> C -> D
     ^         |
     |_________|

Traversal order:

A, B, C, D, B

When we see B again, we know there is a cycle.

This works, but it uses extra memory:

O(n)

We can do better.

Key Insight

Use two pointers moving at different speeds.

This is Floyd’s cycle detection algorithm, also called the tortoise and hare algorithm.

There are two possibilities:

1. No cycle:
   • fast eventually reaches None
2. Cycle exists:
   • fast eventually catches slow

Why Fast Eventually Catches Slow

Suppose the list contains a cycle.

Inside the cycle:

• slow moves one step per iteration
• fast moves two steps per iteration

So relative to slow, the fast pointer gains:

2 - 1 = 1

step per iteration.

That means the distance between them inside the cycle shrinks modulo the cycle length.

Eventually, fast lands on the same node as slow.

So if the pointers ever meet, a cycle must exist.

Example Walkthrough

Consider:

1 -> 2 -> 3 -> 4 -> 5
          ^         |
          |_________|

Initial:

Move:

The pointers meet at node 4.

So a cycle exists.

Algorithm

Initialize:

slow = head
fast = head

Then repeatedly:

slow = slow.next
fast = fast.next.next

Before moving fast, check that:

fast and fast.next

exist.

If at any moment:

slow == fast

return True.

If the loop finishes because fast reaches None, return False.

Correctness

If the list has no cycle, the fast pointer moves toward the end of the list twice as quickly as slow. Since the list is finite and acyclic, fast eventually becomes None or fast.next becomes None. The algorithm then returns False.

Now suppose the list contains a cycle.

Once both pointers enter the cycle, the fast pointer gains one node on the slow pointer during each iteration because it moves two steps while slow moves one. Since the cycle length is finite, this relative distance eventually becomes zero modulo the cycle length, meaning both pointers point to the same node.

Therefore, if a cycle exists, the pointers eventually meet and the algorithm returns True.

Thus, the algorithm correctly detects whether the linked list contains a cycle.

Complexity

Let n be the number of nodes.

Implementation

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

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

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

            if slow == fast:
                return True

        return False

Code Explanation

Both pointers start at the head:

slow = head
fast = head

The loop condition:

while fast and fast.next:

ensures that moving fast by two steps is safe.

Inside the loop:

slow = slow.next

moves one step.

fast = fast.next.next

moves two steps.

If they point to the same node:

if slow == fast:

a cycle exists.

If the loop ends naturally:

return False

then fast reached the end of the list, so no cycle exists.

Why Compare Nodes, Not Values

Suppose two different nodes both contain:

5

That does not mean a cycle exists.

We must compare node identity:

slow == fast

not:

slow.val == fast.val

The algorithm checks whether the pointers reference the same node object.

Testing

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def run_tests():
    s = Solution()

    a = ListNode(3)
    b = ListNode(2)
    c = ListNode(0)
    d = ListNode(-4)

    a.next = b
    b.next = c
    c.next = d
    d.next = b

    assert s.hasCycle(a) is True

    a = ListNode(1)
    b = ListNode(2)

    a.next = b
    b.next = a

    assert s.hasCycle(a) is True

    a = ListNode(1)

    assert s.hasCycle(a) is False

    a = ListNode(1)
    b = ListNode(2)
    c = ListNode(3)

    a.next = b
    b.next = c

    assert s.hasCycle(a) is False

    a = ListNode(1)
    a.next = a

    assert s.hasCycle(a) is True

    print("all tests passed")

run_tests()

Test meaning: