# Tortoise-Hare Algorithm

## Problem
Given a linked list, detect if some cycle exists.

A naive solution is to use hash table to record while traversing the linked list, which requires $O(n)$ time and $O(n)$ space.

In the following section, we will describe an algorithm that solves this problem in $O(1)$ space.

## Algorithm
The algorithm is actually a two pointer algorithm.
We maintain two pointer `fast` and `slow` while traversing the linked list.

Each time, `fast` moves `2` units and `slow` moves `1` unit.

bool has_cycle(node *list_head, int n) {
    // n: #node in the linked list
    node *fast = list_head;
    node *slow = list_head;
    
    for (int step = 0; step < n; step++) {
        fast = fast->next->next;
        slow = slow->next;
        
        if (fast->id == slow->id)
            return true;
    }
    return false;
}

Moreover, to **find the start of the cycle**, we move
`slow` back to `list_head`, and move each pointer `1` unit at a time until they meet. The node where they meet is the start of the cycle.

node *get_cycle_start(node *list_head, int n) {
    node *fast = list_head;
    node *slow = list_head;
    
    for (int step = 0; step < n; step++) {
        fast = fast->next->next;
        slow = slow->next;
        
        if (fast->id == slow->id)
            break;
    }
    
    // no cycle
    if (fast->id != slow->id)
        return 0;
    
    slow = list_head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

## Correctness
It is easy to see that if the cycle exist, then they must meet during the algorithm.

But it's not easy to see that `fast` and `slow` will meet in `n` iterations (i.e. `slow` will meet `fast` before traversing the whole list.)

### Thm 1
> **It suffices to iterate the for loop at most `n` times to see if the cycle exist.**

**proof**
Let `C` be the length of the cycle.

When `slow` enters the cycle, the distance between `slow` and `fast` is at most `C`.

When both `slow` and `fast` move one time, their distance decrease by 1. Hence it takes at most `C` steps before they meet since `slow` enters the cycle.

Therefore, it takes at most `n` steps from the begining to they meet, if the cycle exists.

### Corollary

When `fast` and `slow` meet,
- `slow` walks `x+y` steps
- `fast` walks `x+y+k*C` steps, for some k in N

### Thm 2
> **`get_cycle_start()` correctly finds the start of the cycle.**

**proof**
Let `s` be the number of steps taken until `fast` and `slow` meet. Then by corollary we have
- `s = x+y`
- `2*s = x+y+k*C`

By subtracting the two equations, we have `s = k*C`, which is `x+y = k*C`. This implies that **`x+y` is a multiple of `C`**.

In `get_cycle_start()`, after `slow` and `fast` first meet, `slow` is put back to the list head. After `x` steps, `fast` would have walked `x+y` steps with respect to the start point of the cycle, thus will be at start point of the cycle.

## Example
[Leetcode 287. Find the Duplicate Number
](https://leetcode.com/problems/find-the-duplicate-number/)

## Reference
- https://www.readfog.com/a/1673618932623314944

###### tags: `Algorithm`