Find the length of a loop in a linked list
Tags: computerscience, javascript, beginners
Published: 2020-09-12 22:12:04

---
title: Find the length of a loop in a linked list
published: true
description: Solution for finding the length of a loop in a linked list. Useful for coding interviews and other puzzle solving.
tags: computerscience, javascript, beginners
cover_image: https://dev-to-uploads.s3.amazonaws.com/i/std5oyx5qd0ia3hybjqj.jpg
---
I have been doing some katas, to improve my coding skills.  I am now at 6kyu on [CodeWars](https://www.codewars.com/).
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: 
![](https://i.imgur.com/Rc6RPT5.png)

##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: 

```JavaScript
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:

```JavaScript
    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:

```javascript
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](https://www.codewars.com/kata/52a89c2ea8ddc5547a000863)
[Floyd's Cycle Detection algoritm - clear explanation on hackerrank](https://www.youtube.com/watch?v=MFOAbpfrJ8g&ab_channel=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 :) !