Linked List Cycle

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 {
    let fast = head;
    let slow = head;

    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;
        }
    }
};