Linked List cycle

We will use Floyd's cycle-finding algorithm, also known as tortoise and hare algorithm.

Overview

1. We will use a 2-pointer technique where 1 pointer will be fast and the other pointer will be slow.
2. The whole idea is based on the principle that if there is a cycle in the Linked List, at some point both the pointers will meet each other, else one of them ( or its next ) will be NULL.

Let's implement using Javascript. -

1. The input here will be a Linked List.
2. First of all, we will check if the Linked List is empty or has just 1 node. There will not be any cycle definitely in both of the cases.
3. Next, we will define 2 pointers, as mentioned above. First will be a slow pointer and the second will be the fast pointer i.e. while traversing, when the slow pointer will move one step ahead, the fast pointer will move two steps ahead.
4. We will keep traversing until slow and fast is not equal or one of them ( or its next ) is not NULL.
5. If fast and slow becomes equal, then it means there is a cycle.
6. If either of the slow or fast pointer ( or its next ) becomes NULL, it means there is no cycle in the Linked List.

var hasCycle = function(head) {
    if (head === null || head.next === null) {    // Point 2
        return false;                             // Point 6
    }
    let slow = head.next;                         // Point 3
    let fast = head.next.next;
    while(slow!==fast) {                          // Point 4
        slow = slow.next;
        if (fast == null || fast.next === null) { // Point 4,5
            return false;                         // Point 6
        }
        fast = fast.next.next;
    }
    return true;                                  // Point 5
};

Please note that for point 6, we check only fast node for NULL value because at any point fast will be ahead of slow and it will visit every node before the slow node.