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 steps
- 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
- 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.
- 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
/*
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 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.
*/
/---------------------------------------------------/
/*
SOLUTION
- 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 return *NULL* since
the list is not cycle in the first place
- If it is true that it is a cycle the slow pointer would be at
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 while loop.
provided that our new variable is
not the same as the slow pointer(which should currently be at
a the back of the node that begins the cycle) we keep moving
until the while loop condition becomes true at this point the
we can return the new variable or the slow
*/
function detectCycle(head) {
// Verify if List is a cycle
let fast = head
let slow = head
let verified = false
while (fast && fast.next) {
fast = fast.next.next
slow = slow.next
if (fast === slow) {
verified = true
break
}
}
// if Verified is still fasle then No Cycle is detected
if (!verified) {
return null
}
let start = head
while (start !== slow) {
start = start.next
slow = slow.next
}
return slow
}
// Visual Representation of First Solution
// [3] -> [2] -> [0] -> [-4] -> points to node at position of index 1 to create a cycle
// - Step 1 => verify that list is a cycle
// fast(f) starts at head => [3]
// slow(s) starts at head => [3]
(loop)| 1 | 2 | 3
------|-----------------|------------------|------------------
(cpos)| f = [0], s =[2] | f = [2], s = [0] | f = [-4], s = [-4]
/* At this point slow is at [-4] which points directly to the node that begins that cycle
if we could not verify this then the list is never a cycle and there is no need to proceed
return **NULL**
*/
/* We then initialize another variable that points to the beginning of the list again and loop
again, provided that the variable and the slow pointer are not the same yet we would keep
walking the list until they both meet, wherever they meet is the beginning of the cycle
*/
// start(st) starts at head = [3]
// slow(s) is currently at tail = [-4]
(loop)| 1 | 2(condition fails)
------|-----------------|------------------|
(cpos)| st = [2], s =[2] | return st or s
function detectCycle(head) {
let p1 = head;
let p2 = head;
let lent = lenOfCycle(head)
let node = isCycle(head)
if (node === null) {
return null
}
while (lent > 0) {
p2 = p2.next
lent--
}
while (p1 !== p2) {
p1 = p1.next
p2 = p2.next
}
return p1
}
function lenOfCycle(head) {
let count = 0;
let fast = head;
let slow = head
while (fast && fast.next) {
fast = fast.next.next
slow = slow.next
count++
if (fast === slow) {
break
}
}
return count
}
function isCycle(head) {
let fast = head;
let slow = head;
while (fast && fast.next) {
fast = fast.next.next
slow = slow.next
if(fast === slow) {
return fast;
}
}
return null
}
