# 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](https://leetcode.com/problems/linked-list-cycle/?utm_source=chatgpt.com))

## Examples

Example 1:

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

The tail points back to the node with value `2`.

So the list contains a cycle.

Output:

```python
True
```

Example 2:

```text
1 -> 2
^    |
|____|
```

The second node points back to the first node.

Output:

```python
True
```

Example 3:

```text
1 -> None
```

There is no cycle.

Output:

```python
False
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | `head: Optional[ListNode]` |
| Output | `bool` |
| Goal | Detect whether a cycle exists |
| Important detail | The list structure must not be modified |

Function shape:

```python
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:

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

Traversal order:

```text
A, B, C, D, B
```

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

This works, but it uses extra memory:

```python
O(n)
```

We can do better.

## Key Insight

Use two pointers moving at different speeds.

| Pointer | Speed |
|---|---|
| `slow` | One step at a time |
| `fast` | Two steps at a time |

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:

```text
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:

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

Initial:

| Step | slow | fast |
|---:|---|---|
| `0` | `1` | `1` |

Move:

| Step | slow | fast |
|---:|---|---|
| `1` | `2` | `3` |
| `2` | `3` | `5` |
| `3` | `4` | `4` |

The pointers meet at node `4`.

So a cycle exists.

## Algorithm

Initialize:

```python
slow = head
fast = head
```

Then repeatedly:

```python
slow = slow.next
fast = fast.next.next
```

Before moving `fast`, check that:

```python
fast and fast.next
```

exist.

If at any moment:

```python
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.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each pointer traverses at most a linear number of nodes |
| Space | `O(1)` | Only two pointers are used |

## Implementation

```python
# 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:

```python
slow = head
fast = head
```

The loop condition:

```python
while fast and fast.next:
```

ensures that moving `fast` by two steps is safe.

Inside the loop:

```python
slow = slow.next
```

moves one step.

```python
fast = fast.next.next
```

moves two steps.

If they point to the same node:

```python
if slow == fast:
```

a cycle exists.

If the loop ends naturally:

```python
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:

```python
5
```

That does not mean a cycle exists.

We must compare node identity:

```python
slow == fast
```

not:

```python
slow.val == fast.val
```

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

## Testing

```python
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:

| Test | Why |
|---|---|
| Standard cycle example | Normal cycle detection |
| Two-node cycle | Small cycle |
| Single node without cycle | Minimum acyclic case |
| Multi-node acyclic list | Normal no-cycle case |
| Self-loop | Node points to itself |