• 0

Detect start of a loop in linked list

Problem :

Given a linked list, implement an algorithm which returns the node at the beginning of the loop.

This post is a follow-up of
- JavaScript Linked List Example
- Detect a loop in cyclic/circular linked list.
- Loop Length in cyclic/cicular 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 cyclic/circular linked list.
  • Move p1 at the head of the linked list, and keep p2 at the same location where p1 and p2 met.
  • Move p1, p2 one step at a time, when they will meet again it's the beginning of the loop.
Circular Linked List with Loop size = 4
Circular Linked List with Loop size = 4
Watch the following video to understand the Floyd's cycle-finding algorithm!

This solution is a follow-up of JavaScript Linked List Example. I recommend reading it first, as the following code uses the method from it.

Solution :


'use strict';
function LinkedList () {
this.head = null;
}
LinkedList.prototype.loopBegining = function () {
var p1, p2, isLoop;
p1 = this.head;
p2 = this.head;
// loop detection, basic condition for loop to exist
while (p2.next.next) {
p1 = p1.next;
p2 = p2.next.next;
if (p2 === p1) {
isLoop = true;
break;
}
}
// Loop begining detection
if (isLoop) {
p1 = this.head;
while (p1 !== p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
} else {
return;
}
};
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.loopBegining()); // Object {data: 3, next: Object}
// Remove circular dependency
//L1.head.next.next.next.next.next.next = null;
//console.log(L1.loopBegining());
view raw loopBegining.js hosted with ❤ by GitHub

Output :

Sample console output
Sample console output

References :