# LeetCode 142: Linked List Cycle II

## Problem Restatement

We are given the head of a linked list.

If the linked list contains a cycle, return the node where the cycle begins.

If there is no cycle, return `None`.

LeetCode internally represents the cycle using an index `pos`, where the tail points back to the node at index `pos`. This value is not passed into the function. ([leetcode.com](https://leetcode.com/problems/linked-list-cycle-ii/?utm_source=chatgpt.com))

## Examples

Example 1:

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

The cycle begins at the node with value `2`.

Output:

```python
node with value 2
```

Example 2:

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

The cycle begins at the node with value `1`.

Example 3:

```text
1 -> None
```

There is no cycle.

Output:

```python
None
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | `head: Optional[ListNode]` |
| Output | Node where the cycle starts, or `None` |
| Important detail | Return the node itself, not the value |
| Constraint | Do not modify the linked list |

Function shape:

```python
class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        ...
```

## Relation to LeetCode 141

LeetCode 141 only asks:

```text
Does a cycle exist?
```

LeetCode 142 asks a harder question:

```text
Where does the cycle begin?
```

We still use Floyd’s tortoise and hare algorithm.

But after detecting the cycle, we perform one more step to locate the entry node.

## First Step: Detect Whether a Cycle Exists

Use two pointers:

| Pointer | Speed |
|---|---|
| `slow` | One step |
| `fast` | Two steps |

If no cycle exists:

```python
fast
```

eventually reaches `None`.

If a cycle exists:

```python
slow == fast
```

at some node inside the cycle.

This part is identical to LeetCode 141.

## Key Insight

After the two pointers meet:

1. Move one pointer back to the head.
2. Keep the other pointer at the meeting point.
3. Move both pointers one step at a time.
4. The node where they meet again is the cycle entry.

This looks surprising at first.

The reason comes from the distance relationships inside the cycle.

## Mathematical Proof

Define:

| Symbol | Meaning |
|---|---|
| `a` | Distance from head to cycle entry |
| `b` | Distance from cycle entry to meeting point |
| `c` | Remaining cycle length |

So the total cycle length is:

```python
b + c
```

When the pointers meet:

- `slow` traveled:

```python
a + b
```

- `fast` traveled:

```python
2(a + b)
```

But `fast` also traveled exactly one extra full cycle more than `slow`.

So:

```python
2(a + b) = a + b + k(b + c)
```

for some integer `k >= 1`.

Simplify:

```python
a + b = k(b + c)
```

Rearrange:

```python
a = k(b + c) - b
```

For the first meeting, think of one cycle difference:

```python
a = c
```

modulo the cycle length.

That means:

- starting from the head and walking `a` steps reaches the cycle entry
- starting from the meeting point and walking `c` steps also reaches the cycle entry

So if:

1. one pointer starts at the head
2. one pointer starts at the meeting point
3. both move one step at a time

they meet exactly at the cycle entry.

## Example Walkthrough

Consider:

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

The cycle entry is node `3`.

Suppose the pointers meet at node `5`.

Now:

- move one pointer to the head
- keep one pointer at `5`

Move both one step:

| Step | Pointer A | Pointer B |
|---:|---|---|
| `0` | `1` | `5` |
| `1` | `2` | `3` |
| `2` | `3` | `4` |
| `3` | `4` | `5` |
| `4` | `5` | `3` |

Depending on cycle length and meeting location, they eventually synchronize at the cycle entry.

The formal proof guarantees this.

## Algorithm

Phase 1:

1. Use slow and fast pointers.
2. Detect whether a cycle exists.

Phase 2:

If a meeting occurs:

1. Set:

```python
ptr1 = head
ptr2 = meeting_node
```

2. Move both one step at a time.
3. When they meet, return that node.

If no cycle exists, return `None`.

## Correctness

If the linked list has no cycle, the `fast` pointer eventually reaches `None`, so the algorithm correctly returns `None`.

Now suppose the list contains a cycle.

By Floyd’s cycle detection argument, the `slow` and `fast` pointers eventually meet inside the cycle.

Let:

| Symbol | Meaning |
|---|---|
| `a` | Distance from head to cycle entry |
| `b` | Distance from cycle entry to meeting point |
| `L` | Cycle length |

At the meeting point, the fast pointer has traveled one whole cycle more than the slow pointer, so:

```python
2(a + b) = a + b + kL
```

which simplifies to:

```python
a + b = kL
```

Therefore:

```python
a = kL - b
```

This means the distance from the meeting point to the cycle entry equals the distance from the head to the cycle entry modulo the cycle length.

So if one pointer starts at the head and another starts at the meeting point, and both move one step at a time, they meet exactly at the cycle entry.

Therefore, the algorithm correctly returns the node where the cycle begins.

## Complexity

Let `n` be the number of nodes.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Linear traversal |
| Space | `O(1)` | Only pointer variables are used |

## Implementation

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

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

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

            if slow == fast:
                ptr1 = head
                ptr2 = slow

                while ptr1 != ptr2:
                    ptr1 = ptr1.next
                    ptr2 = ptr2.next

                return ptr1

        return None
```

## Code Explanation

Initialize two pointers:

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

Move them at different speeds:

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

If they meet:

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

a cycle exists.

Now:

```python
ptr1 = head
ptr2 = slow
```

One pointer starts from the head.

The other starts from the meeting point.

Move both one step:

```python
while ptr1 != ptr2:
    ptr1 = ptr1.next
    ptr2 = ptr2.next
```

When they meet again:

```python
return ptr1
```

that node is the cycle entry.

If no meeting ever occurs:

```python
return None
```

the list has no cycle.

## Why Returning `slow` Immediately Is Wrong

The first meeting point is not necessarily the cycle entry.

Example:

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

The cycle entry is `3`.

But the first meeting may happen at `4` or `5`.

So we need the second phase to locate the true entry node.

## 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.detectCycle(a) == b

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

    a.next = b
    b.next = a

    assert s.detectCycle(a) == a

    a = ListNode(1)

    assert s.detectCycle(a) is None

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

    a.next = b
    b.next = c

    assert s.detectCycle(a) is None

    a = ListNode(1)
    a.next = a

    assert s.detectCycle(a) == a

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard cycle | Cycle entry in the middle |
| Two-node cycle | Entry at head |
| Single node without cycle | Smallest acyclic case |
| Multi-node acyclic list | No cycle |
| Self-loop | Node points to itself |