Find the length of a loop in a linked list

I have been doing some katas, to improve my coding skills. I am now at 6kyu on CodeWars.
This week my interesting problem was :

You are given a node that is the beginning of a linked list. This list always contains a tail and a loop. Your objective is to determine the length of the loop. The loop looks like this:

How to Solve

There are 2 parts of this question:

1. Figure out when you are in the loop
2. Count the nodes in the loop

Figure when you are in the loop

After a quick google, I have discovered the Floyd's Cycle Detection algoritm - which, as it says, finds whether you are stuck in a loop. You can also use it to find exactly where the start of the loop is, but this is outwith the scope of this question.

The basic idea is that you have 2 pointers:

• one moving to the next node by 1 ( slow pointer)
• second pointer which moves by 2 nodes (fast pointer)

If the list you are in is indeed a loop, both should meet at some point as both will be going round-and round.

The code therefore is as follows:

function getNodeInLoop(node){
   let slow = node;
   let fast = node.next;

//problem assumes there is always going to be a loop
//so no need to check
   while(slow !== fast){ 
        slow = slow.next; //move by 1
        fast = fast.next.next; //move by 2
    }

  return slow; 
}

We therefore return a known location of a node in the loop.

Count

We can start counting the nodes! We take our node in which both slow and fast pointers matched (in here seenNode) as treat it as the root node in the loop. We use a "pointer" variable to keep track of there we are in our while loop and "count" to count the number of nodes we have went through:

    let size = 1
    let seenNode = getNodeInLoop(node); 
    let pointer = seenNode.next; 

    while(pointer !== seenNode ){
        size++; 
        pointer = pointer.next;
    }

    return size;

Solution

The Full solution is as follows:

function loop_size(node){
    let size = 1;
    let seenNode = getNodeInLoop(node); 
    let pointer = seenNode.next; 

    while(pointer !== seenNode ){
        size++; 
        pointer = pointer.next;
    }

    return size;
}

function getNodeInLoop(node){
   let slow = node;
   let fast = node.next;

//problem assumes there is always going to be a loop
//so no need to check
   while(slow !== fast){ 
        slow = slow.next; //move by 1
        fast = fast.next.next; //move by 2
    }

  return slow; 
}

Ta-dah!

Links

CodeWars Question
Floyd's Cycle Detection algoritm - clear explanation on hackerrank

p.s I am not sure why but codewars does not like separate functions for a solution, and therefore most of my coding solutions are just written as one function.
p.p.s As always, this is only my solution and I know there are other implementations out there. Feel free to comment your one to start a discussion :) !

Comments

[ali mg]

Thank you.
also i would appreciate any explanation from anyone helping me understand the code below which i got from loging the slow, fast vars in the console. ( i understand this is the node but i would want to understand it )
<ref *1> Node {
getNext: [Function (anonymous)],
setNext: [Function (anonymous)],
next: [Circular *1]
}