Detecting Loops in Singly Linked Lists

A recent toy problem had me trying to determine if a loop exists in a given linked list. At first this was a difficult-sounding problem, but after some white-boarding, I determined a simple solution for it.

A good analogy for the algorithm is to imagine two horses running around a track. Suppose they are both running at consistent speeds, but horse 2 is running slightly faster than horse 1. If they are running on a straight track with an endpoint (like a linked list whose last node points to null), horse 2 will reach the end, shortly followed by horse 1. However, if they are running on a circular track (like a loop), after a while (perhaps even several laps), horse 2 will pass horse 1, since it’s running faster.

To translate this into pseudocode, if we set two iterators to loop through the linked list, and make one of the iterators iterate faster than the other, we can determine if a loop exists by checking whether or not the two iterators are ever equal to each other. If they ever do equal each other, we can return a value of true (for it is true that a loop exists), and if they end up at null (the finish line in the first example), return false.

The issue now arises that we have to translate this to actual code.

I knew I would need a loop, and since nodes are objects, I chose a while loop, and I started each of my horses one node apart:

let hasCycle = linkedList => {
let count1 = linkedList,
count2 = linkedList.next;
while () {
}
};

Next, I’ll set a results variable and a base case to let us break out of the loop if the two horses do line up:

let hasCycle = linkedList => {
let result = false;
let count1 = linkedList,
count2 = linkedList.next;
while (count2.next) {
if (count1.value === count2.value) {
result = true;
break;
}
}
return result;
};

We almost have it, but we’ve got to make sure our horses are moving down the track after each iteration, keeping it mind that one must go faster than the other:

let hasCycle = linkedList => {
let result = false;
let count1 = linkedList,
count2 = linkedList.next;
while (count2.next) {
if (count1.value === count2.value) {
result = true;
break;

}
count1 = count1.next;
count2 = count2.next.next;

}
return result;
};

This will work for us in most cases, but we’ll hit some problems if the length of the list is two short. An easy (albeit not particularly elegant) solution for this is to just add some edge cases up front:

let hasCycle = linkedList => {
let result = false;
if (!linkedList.next || !linkedList.next.next || !linkedList.next.next.next) {
return result;
}

let count1 = linkedList,
count2 = linkedList.next;
while (count2.next) {
if (count1.value === count2.value) {
result = true;
break;
}
count1 = count1.next;
count2 = count2.next.next;
}
return result;
};

The above solution will result in a boolean specifying whether there is a loop in a given linked list (and in linear time!)

That’s all for tonight!