142. Linked List Cycle II - LeetCode Fastest Solution
Updated: Jan 17
Hello Code Recipian! In our last article we discussed the solution for LeetCode 141. Linked List Cycle. Today let's solve an extension of this problem, LeetCode 142. Linked List Cycle II. If you haven't read the earlier article yet, we strongly recommend reading it first before diving into this one.
This article is part of our LeetCode problem solutions series. So hey, don't stop here! Make sure you check them out after you are done here!
Problem Statement: Linked List Cycle II
Given the head node of a linked list, return the node where the cycle starts. If cycle does not exist, return null.
Do not modify the linked list.
Example 1
Input: head = [3, 2, 0, -4]
Output: Node with value 2
Explanation: Cycle exists in the given linked list and it begins at node with value = 2.

Example 2
Input: head = [1, 2, 3, 4]
Output: Null
Explanation: Linked list does not contain any cycle.

Constraints
The number of the nodes in the list is in the range [0, 10^4].
-10^5 <= Node.val <= 10^5
Solution
This problem can be efficiently solved using the Floyd's Cycle Detection algorithm that we discussed in our previous article.
Algorithm
Initialization:
Initialize two pointer variables: slow, fast and point both of them to the head node of the given linked list.
Linked list traversal (detect cycle):
Traverse through the linked list using the slow, fast pointers. In each iteration perform the following steps:
Move the slow pointer one node at a time.
Move the fast pointer two nodes at a time.
Check if slow pointer is equal to fast pointer:
If at any point during the traversal, if slow is equal to fast, it means we have found a cycle.
Find the cycle start node by calling cycleStart() function.
Return the cycle start node as result.
If slow is not equal to fast, continue iterating.
Finding the cycle start node (cycleStart() function):
Once a cycle is found, in order to get the starting node of the cycle:
Let the fast pointer point to the node where slow and fast met.
Point the slow pointer to the linked list head node.
Now move both slow and fast pointers together, 1 step at a time. The node at which slow and fast meet again is the starting node of the cycle. Hence, return this node as result.
Return null result:
If the execution comes out of the main loop without returning, it means the given linked list does not contain a cycle. Therefore return null node as result.
Why this approach works
In order to get the result we point slow to head and fast to the meeting point of slow and fast and they move them by one step to meet at the starting node. Let's understand the intuition behind this:
Let's denote the following:
L: Distance from the head node to the node at which the cycle starts.
C: Be the length of the cycle.
K: Distance from the start of the cycle (cycle start node) to the node where slow and fast pointers meet.

Since fast pointer moves at twice the speed of slow pointer, by the time they meet, fast pointer would have traversed twice the distance of slow pointer.
Let's denote the total distance traversed by the slow pointer till the meeting point as d. Then the distance traversed by the fast pointer to reached the meeting point is 2*d.
At the point where two pointers meet:
Distance travelled by slow pointer = L + K.
Distance travelled by fast pointer = L + K + n * C. n is the number of full cycles (laps) completed by the fast pointer within the cycle before meeting.
Setting up the equation:
2 * (L + K) = L + K + n * C
Simplifying the above equation we get:
L + K = n * C
or
L = n * C - K
The above equation means, the distance from head of the list to the start of cycle, is equal to the distance from the meeting point of slow and fast to start of the cycle. And that is why, when we position slow pointer at the head and fast pointer at the meeting point and move them one node at a time, they meet at the start node of the cycle.
Simulation
Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses:
Code
Go Solution
Python Solution
Java Solution
JavaScript Solution
TypeScript Solution
C++ Solution
C# Solution
C Solution
PHP Solution
Kotlin Solution
Swift Solution
Ruby Solution
Scala Solution
Rust Solution
Complexity Analysis
Time Complexity
Detecting the cycle:
Detecting the cycle takes O(n) time complexity (to understand this in detail please to refer our previous article), where n is the total number of nodes in the linked list.
Finding cycle start node:
For finding the cycle start node we initially point slow to head node and fast to the meeting point node and then move slow and fast again until they meet: This takes O(n-C) time, C is the length of the cycle.
Overall time complexity:
Combining all the above analysis, overall time complexity is O(n) + O(n-C) = O(n).
Space Complexity
Space complexity of this algorithm is O(1) as we are not using any extra space.
That brings us to the end of article. Do check out our other articles on LeetCode problem solutions. If you found this article helpful please consider signing up to Code Recipe.
That's all for today, see you next time! Happy Coding!
Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.
Hello Coders!
Code Recipe is now on YouTube! For videos on latest topic visit our YouTube channel: Code Recipe
Visit Now: https://www.youtube.com/@coderecipeofficial
Do not forget to subscribe to our channel if you find the videos useful. Your support means a lot to us!
Happy Learning. Ba bye! 😊