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:

Last updated