# Floyd's cycle-finding algorithm The problem is, given the head of a linked list, detect if the linked list has a cycle.

The brute force way to do this is to save all the node in a map when iterating the whole linked list. Then check if new node has been visited before. This method is ok, but it may takes a lot of memory.

The more efficient way to solve this problem is to use Floyd's cycle-finding algorithm.

The idea is very simple. We use two pointers when iterating the linked list, one should walk faster the other. The key is, if there is a cycle, then at some point, the faster pointer should meet the slower one.

``````class ListNode {
val: number;
next: ListNode | null;
constructor(val?: number, next?: ListNode | null) {
this.val = (val === undefined ? 0 : val);
this.next = (next === undefined ? null : next);
}
}

function hasCycle(head: ListNode | null): boolean {

while (fast !== null && fast.next !== null) {
fast = fast.next.next; // faster poiner, walk two steps every time
slow = slow.next; // slow pointer, walk one step every time
if (fast === slow) {
// when two pointers meet, then there is a cycle
return true;
}
}
return false;
};
``````

## Happy Number

A happy number is a number which eventually reaches 1 when replaced by the sum of the square of each digit. We don't need to know why, we just need to know if a number is not a happy number, then there must be a cycle when computing its next value constantly. So this problem is a cycle detecting problem and can be solved by Floyd's cycle-finding algorithm as well.

``````function next(n: number): number {
let result = 0;
while(n > 0) {
result += Math.pow(n % 10, 2);
n = ~~(n / 10);
}
return result;
}

function isHappy(n: number): boolean {
let fast = n;
let slow = n;

while(true) {
fast = next(next(fast));
slow = next(slow);

if (fast === 1) return true;
if (fast === slow) {
return false;
}
}
};
``````