How does finding a cycle start node in a cycle linked list work?
Data Structures & Algorithms practice on Codemia
Step through 300+ coding interview problems with animated visualisers that show the data structure changing as the code runs. The Blind 75 are free.
Introduction
In the context of data structures, a linked list is a series of nodes where each node contains data and a pointer to the next node in the sequence. A common problem with linked lists is detecting cycles, which occur when a node's next reference points back to a previous node in the list, creating a loop. Identifying the start of this cycle can help prevent errors in computations and data manipulations involving linked lists.
This article explores how to detect the starting node of a cycle in a linked list, using Floyd's Tortoise and Hare algorithm. This approach is efficient, operating in O(n) time complexity with O(1) space complexity.
Floyd's Tortoise and Hare Algorithm
Concept
Floyd's Tortoise and Hare algorithm is a two-pointer approach that involves two markers moving through the linked list at different speeds. Here's how it works:
- Two Pointers: We use two pointers,
slow(tortoise) andfast(hare). - Movement:
slowmoves one step at a time, whilefastmoves two steps. - Detection of Cycle: If there is a cycle,
fastandslowwill eventually meet within the cycle. - Finding Cycle Start: Once a meeting point is identified, keep one pointer at the meeting position and reset the other pointer to the start of the linked list. Move both pointers one step at a time. The point at which they meet again is the start of the cycle.
Technical Explanation
- Initialization:
- Begin with
slowandfastpointers both pointing to the head of the linked list.
- Cycle Detection:
- Iterate through the list, moving the pointers with their respective speeds (
slowby one andfastby two). - If
fastbecomesnullorfast.nextbecomesnull, the list has no cycle. - If
slowequalsfast, a cycle exists.
- Locating Cycle Start:
- Reset
slowto the head of the list, keepingfastat the meeting point. - Move both pointers at the same speed (one step at a time).
- The point where they meet again is the start of the cycle.
Code Example
Here is a Python implementation:
Example
Consider the following linked list example:
- One element (2) links back to another element (1), forming a cycle:
By applying the algorithm, the cycle is detected, and the start node (node with value 2) is identified.
Summary Table
| Step | Description | Details |
| Initialization | Start slow and fast at head | Pointers: slow, fast |
| Cycle Detection | Move slow by one, fast by two | Detect meeting point |
| Cycle Verification | If fast or fast.next is null, no cycle | Cycle doesn't exist |
| Locate Cycle Start | Reset one pointer to head, keep one at meeting point Advance both by one | Meeting point is start |
Conclusion
Floyd's Tortoise and Hare algorithm is a clever technique for detecting cycles in linked lists. By effectively managing pointers and leveraging the inherent properties of cycles, it offers a straightforward yet powerful solution. Understanding this approach is crucial for tackling problems involving cycle detection in linked data structures.
Related reading
- How does Firefox's 'awesome' bar match strings?
- How does Google recognizes adult content with safesearch?
- How does Hibernate's batch-fetching algorithm work?
- How does LCP help in finding the number of occurrences of a pattern?
- How does heap compaction work quickly?
- How does Java implement hash tables?
- How does one divide a big integer by another big integer?
- How does one find the largest consecutive set of numbers in a list that are not necessarily adjacent?

DSA Fundamentals
Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.
View the courseData Structures & Algorithms practice on Codemia
Step through 300+ coding interview problems with animated visualisers that show the data structure changing as the code runs. The Blind 75 are free.