Detect LinkedList Cycle Leetcode Solution with Explanation and Illustrations

If you are curious and you would like to take a look at the question yourself, you can find it here

In this very brief article, we would go over my approach to solving this question using beautiful illustrations that will effectively capture the idea behind the solution so stick with me to the end.

Before we dive directly into the solution to the question, let’s talk about the very famous two-pointer technique used in solving some questions that involve linear data structures like Arrays and LinkedList.

The Two Pointer Technique(TPT)

If you perform a quick google search, you would get a lot of explanations about the two pointer technique, this is partly due to its ability to help programmers keep a reference to 2 elements in a linear data structure while iterating once thus giving the opportunity to avoid O(n²) operations in certain scenarios, but also it is a popular choice for solving LinkedList related problems that require iterating a LinkedList.

We would be talking about TPT in the context of LinkedList

The two-pointer technique sometimes also called the hare and tortoise technique entails having two pointers(fast and slow) variables actually, that start at the same position in a LinkedList but while working through the list the fast pointer moves twice as fast as the slow pointer as Illustrated below.

This is usually very useful in LinkedList in that it allows us to detect a cycle in a LinkedList which is exactly what the question we want to solve later is about

What is a cycle in a LinkedList?

A cycle occurs in a LinkedList when the tail node points to another node somewhere in the list or at the beginning of the list as illustrated below.

Using the two-pointer technique, when a LinkedList is a cycle, although the two-pointers(fast and slow) move at different speeds they would eventually meet at some point while walking through the list no matter the length of the list as Illustrated below.

Have we reached the solution already?

Hell yeah, we are here. Let’s take a look at the question and come up with potential solutions.

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that the tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that “pos” is not passed as a parameter.

Do not modify the linked list.

If we understand the question perfectly, we are given the head of a Singly-LinkedList and we are asked to walk through the list and get the node that makes this list a cycle. The point in which the List becomes a cycle is that point where the tail node connects to a node within the list as illustrated below.

Internally Leetcode uses “pos” to reference the node where the tails node points in order to create a cycle. Up until now, I do not know how to create this manually so that I can run my own custom test using my custom implementation of a Singly-LinkedList that you can find here.

Initially, I thought this is easy, because from the Illustration below if there is a cycle in a LinkedList, given the head, if we have two pointers, one that moves twice as fast as the other we already know that they would eventually meet but what is even more interesting is that in most cases they would meet at the node whose next is the node that started the cycle(which is usually the tail node).

What this means is that if we called the “meet point’s” next value we would get our guy and that would be our solution.

But what about this specific case?

Using the first solution, this special case would not work, at least not for all cases as we have seen but this solution would help us in coming up with an actual solution.

The solution

The solution to this problem requires 3

1. First, verify that the LinkedList is a cycle by looping using the two-pointer technique from the head of the list till the two-pointers meet, if they never meet we return *NULL* since the list is not a cycle in the first place
2. If it is true that it is a cycle the slow pointer would be at the back of the node that starts the cycle, we would then declare a new variable pointing to the head again and loop through using a while loop.
3. provided that our new variable is not the same as the slow pointer(which should currently be at the back of the node that begins the cycle) we keep moving until the while loop condition becomes true, at this point we can return the new variable or slow

Let’s look at a visual representation of the solution before we proceed to write the actual code implementation

Here is a JavaScript version of the solution