Statementâ–¼
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
A cycle exists 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 denotes the node’s index to which the tail’s next pointer is connected.
Constraints:
The number of the nodes in the list is in the range
[0,104] .−105≤ Node.value≤105 posis -1 or a valid index in the linked list.
Note: The
posparameter isn’t passed as a parameter.
Solution
We use the fast and slow pointers technique to detect the start of a cycle in a linked list as it efficiently detects cycles in linked lists. The fast pointer advances two steps at a time, while the slow pointer advances one step. If the linked list has no cycle, the fast pointer will reach the end without meeting the slow pointer. However, if a cycle exists, the fast pointer will eventually catch up to the slow pointer, confirming the presence of a cycle. This meeting point provides the basis for determining the exact node where the cycle begins.
Let’s go through the algorithm to see how we will reach the solution:
Initialize two pointers,
fastandslow, that point to the head of the linked list.Traverse the linked list using these two pointers:
The
slowpointer moves only one node forward, while thefastpointer moves two nodes forward (skipping a node).If the
fastpointer reaches NULL, we have reached the end of the linked list, and no cycle exists.However, if both
slowandfastpointers become equal, we have reached a node within the cycle.To find the node where the cycle starts, reset one of the pointers to the head of the linked list and continue iterating the linked list using the pointers, with both moving one node forward in each iteration.
The node where these pointers become equal again is where the cycle starts.
Return this node, as this is the start of the cycle.
Let’s look at the illustration below to better understand the solution.