141. Linked List Cycle

Reformulated question¶

Detect whether a singly linked list contains a cycle.

• A cycle means following next eventually reaches a previously visited node again.
• Return True if a cycle exists, else False.

Example:

[3 -> 2 -> 0 -> -4]
      ^          |
      |__________|
output: True

Key trick¶

Use two pointers moving at different speeds.

• slow moves 1 step.
• fast moves 2 steps.
• If there is a cycle, they must meet.
• If fast reaches None, there is no cycle.

Trap¶

Common mistakes:

• Comparing node values instead of node identity.
• Using a set of values, which fails when values repeat.
• Forgetting edge cases like empty list or one node pointing to itself.
• Missing the constant-memory follow-up by using a visited set.

Why this question is interesting¶

It tests whether you can exploit structure instead of extra memory.

• Brute force with visited nodes is easy.
• Floyd's cycle detection is the real interview answer: simple, fast, and \(O(1)\) space.

Solve the problem with idiomatic Python¶

from typing import Optional
from utils import ListNode

class Solution:
    def hasCycle(self, head: Optional["ListNode"]) -> bool:
        # Floyd's tortoise and hare.
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True

        return False

Pytest test¶

import pytest
from utils import ListNode, list_build_cyclic

@pytest.mark.parametrize(
    ("values", "pos", "expected"),
    [
        ([], -1, False),
        ([1], -1, False),
        ([1], 0, True),
        ([1, 2], -1, False),
        ([1, 2], 0, True),
        ([1, 2], 1, True),
        ([3, 2, 0, -4], 1, True),
        ([1, 2, 3, 4], -1, False),
        ([1, 2, 3, 4], 2, True),
        (
            [-21, 10, 17, 8, 4, 26, 5, 35, 33, -7, -16, 27, -12, 6, 29, -12, 5],
            -1,
            False,
        ),
    ],
)
def test_has_cycle(values, pos, expected):
    head = list_build_cyclic(values, pos)
    assert Solution().hasCycle(head) is expected

Comment my solution¶

Your seen solution is correct but not the best interview answer.

• Good:

  • It correctly tracks node identity with id(curr).
  • It avoids the repeated-value bug.

• Less good:

  • It uses \(O(n)\) extra space.
  • In interviews, Floyd's algorithm is usually expected because of the follow-up.

Your SolutionMaxListNumber is not valid.

• It relies on the problem constraint instead of the list structure.
• It would give wrong answers if constraints changed.
• Interviewers usually reject solutions based on hidden bounds like this.

Your test has one bug.

• When values == [], head = nodes[0] would fail.
• Better to use a helper that returns None for an empty list.

from typing import Optional
import pytest
from utils import ListNode


class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head is None:
            return False
        curr = head
        seen = set()
        while curr:
            if id(curr) in seen:
                return True
            seen.add(id(curr))
            curr = curr.next
        return False

class SolutionMaxListNumber:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # using number of nodes constraint
        curr = head
        for i in range(10**4 + 1):
            if curr is None:
                return False
            curr = curr.next
        return True


@pytest.mark.parametrize(
    ("values", "pos", "has_cycle"),
    [
        ([3,2,0,-4], 1, True),
        ([1,2], 0, True),
        ([1], 0, True),
        ([1], -1, False),
        ([1, 2, 3], -1, False),
        # this following case failed on leetcode
        # this shows that values can be equal (here it's -21 appearing twice)
        ([-21,10,17,8,4,26,5,35,33,-7,-16,27,-12,6,29,-12,5,9,20,14,14,2,13,-24,21,23,-21,5], -1, False)
    ]
)
def test_hasCycle(values, pos, has_cycle):
    nodes = [ListNode(v) for v in values]
    for n, nxt in zip(nodes[:-1], nodes[1:]):
        n.next = nxt
    if pos != -1:
        nodes[-1].next = nodes[pos]
    head = nodes[0]
    assert Solution().hasCycle(head) == has_cycle
    assert SolutionMaxListNumber().hasCycle(head) == has_cycle

Extra¶

Proof that fast must meet slow in a cyclic list¶

Let:

• slow move 1 node per iteration.
• fast move 2 nodes per iteration.
• The list have:
  • a non-cyclic prefix of length \(\mu\)
  • a cycle of length \(\lambda\)

We prove that if a cycle exists, then after some iteration fast is slow.

Step 1: Both pointers eventually enter the cycle¶

• slow enters the cycle after \(\mu\) steps.
• fast also enters the cycle no later than that.

So after at most \(\mu\) iterations, both pointers are inside the cycle.

Step 2: Once both are in the cycle, only positions modulo \(\lambda\) matter¶

Inside the cycle, number positions as:

• \(0, 1, 2, \dots, \lambda - 1\)

and compute positions modulo \(\lambda\).

Suppose both pointers are in the cycle at some iteration.

• If slow advances by 1, its position changes by \(+1 \pmod{\lambda}\).
• If fast advances by 2, its position changes by \(+2 \pmod{\lambda}\).

So the difference

changes by

because fast gains exactly 1 node on slow each iteration.

Step 3: The difference must become 0¶

The possible values of \(d_t\) are only:

and each iteration adds 1 modulo \(\lambda\).

So starting from any initial difference \(d\):

After at most \(\lambda\) iterations, this sequence hits 0.

When \(d_t = 0\):

so both pointers are on the same node.

Therefore, fast is slow.

Equivalent algebraic proof¶

After \(t\) iterations from the head:

• slow has moved \(t\) steps.
• fast has moved \(2t\) steps.

Once both are in the cycle, being on the same node means their traveled distances differ by a multiple of the cycle length:

So they meet whenever \(t\) is a multiple of \(\lambda\), after both have entered the cycle.

Such a \(t\) always exists, for example some multiple of \(\lambda\) with \(t \ge \mu\).

Conclusion¶

If the list has a cycle:

• both pointers eventually enter it,
• inside the cycle fast gains 1 node per iteration modulo the cycle length,
• so the relative gap must become 0 in at most \(\lambda\) more iterations.

Hence fast must eventually catch slow.