• 0

Find loop length in a cyclic/circular linked list

Input :

A linked list

Output:

An integer

Circular Linked List with Loop size = 4
Circular Linked List with Loop size = 4

This post is a follow-up of
- JavaScript Linked List Example
- Detect a loop in cycliccircular linked list.
I recommend reading those posts first, as the following code uses the methods from it.

Logic:

  • Find the loop, using the same logic Detect a loop in cycliccircular linked list.
  • Move p2 one step at a time keeping p1 at a fixed location.
  • Use a loopLength variable to keep track of loop length.
  • When p1 === p2 return the loopLength.
Watch the following video to understand the Floyd's cycle-finding algorithm!

Solution:


'use strict';
function LinkedList () {
this.head = null;
}
LinkedList.prototype.loopLength = function () {
var isLoop, loopLength;
var p1, p2;
isLoop = false;
loopLength = 1;
p1 = this.head;
p2 = this.head;
while (p2.next.next) {
p2 = p2.next.next;
p1 = p1.next;
if (p1 === p2) {
isLoop = true;
break;
}
}
if (isLoop) {
p2 = p2.next;
while (p1 !== p2) {
loopLength++;
p2 = p2.next;
}
return loopLength;
} else {
return 0;
}
};
var L1 = new LinkedList();
var testData = [1,2,3,4,5,6];
testData.forEach(el => L1.insertNodeAtTail(el));
// Create a circular linked list
L1.head.next.next.next.next.next.next = L1.head.next.next;
console.log(L1.loopLength()); // 4
// Remove circular dependency
L1.head.next.next.next.next.next.next = null;
console.log(L1.loopLength()); // 0
view raw findLoopLength.js hosted with ❤ by GitHub

References :