Loopy LinkedList & Two Pointers pattern

Question: Given a linked list, determine if it has a cycle in it.

The question asks us to determine if there's a cycle in a given LinkedList.

Will this knowledge help you in real life? Most probably yea!

Consider this, you're developing an application, and an API calls another API which in turn calls another an so on, you notice that somewhere along the line you called a wrong API and now this API calling chain is going on endlessly. How will you determine
1> was it actually you're a mistake?
2> where did you foo up?

So with that out of the way, let's take a look at give linked list.

In the above-linked list as you can see there's a loop, so how to detect it?

Here I want you to observe that if there's a loop, then the same value will repeat, this points towards the possibility of using Sets/HashMaps. We shall store the nodes in a Set and traverse through the LinkedList if we come across a node already present in the LinkedList, it means we have a loop, else if we reached the end of LinkedList then there is no loop in LinkedList.

var hasLoop = function(head) {
    let set = new Set();
    while(head!=null){
        if(set.has(head)){
            return true;
        }
        set.add(head);
        head = head.next;
    }
    return false;
};

But can you do better?
Here even though the algorithm works in O(n) time, it takes O(n) space.

Here I want to introduce a cycle detection algorithm aka Floyd's tortoise and hare algorithm.

1> The algorithm states that take two pointers, one tortoise which moves slowly, one hare which moves fast.
2> The two pointers will start at the same head position, the tortoise will go to the next node while the hare moves twice the speed jumping a node on each iteration.
3> If there is no loop then hare will reach the end.
4> If there is a loop then hare and tortoise will be stuck in the loop and they'll meet at some point.

Step 1> Tortoise and hare start at same point

Step 2> Tortoise goes to next node while hare skips one node

Step 3> They repeat the same pattern.

Step 4> on next iteration they meet !

It's that simple! The average running time is O(n) and space complexity is O(n)

var hasCycle = function(head) {
  let fast = head;
  let slow = head;

  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;

    if (fast === slow) return true;
  }
  return false;
};

Follow up: get the node where the cycle occurs.

In this case we follow the exact same steps as above but once the hare and tortoise nodes meet, we ask hare to hold his horse, go back towards the head of LinkedList and instead of skipping a node, traverse in order without skipping any nodes.

step 1> move towards the head

step 2> start traversing tortoise and hare pointers traversing one node at a time

step 3> The node where both pointers meet is the answer.

var detectCycle = function(head){
    let slow = head;
    let fast = head;
    while(fast && fast.next && fast.next.next){
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast){
            fast= head;
            while(slow !== fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
}

That's it! Thanks if you made it till here!

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/tree/master/problems