Comment on page

ID: 141; easy

## Solution 1 (Go)

/**
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
m := make(map[*ListNode]bool)
if _,found := m[head]; found {
return true
}
}
return false
}

## Solution 2 (Go)

/**
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
for tortoise != nil && hare != nil && hare.Next != nil {
tortoise = tortoise.Next
hare = hare.Next.Next
if tortoise == hare {
return true
}
}
return false
}

## Solution 3 (Java)

/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @return: True if it has a cycle, or false
*/
return false;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
}

### Floyd's tortoise and hare cycle-finding algorithm

The tortoise move by 1 step each time and the hare moves by 2 steps at a time. If there is a cycle, the hare will eventually catch the tortoise at a position.
A simple idea of the proof can be tracking the gap between the tortoise and the hare. By construction, the gap increases by 1 each iteration. Eventually, the gap with become n, where n is the number of elements in the cycle (not the whole list). This is the time when the tortoise and the hare meet. More proofs: