LinkedListProblem 5 of 36
Find the starting point of the loop
Find the Starting Point of the Loop
Problem Statement
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.
Example
Input: head = [3, 2, 0, -4], pos = 1
3 -> 2 -> 0 -> -4
↑ |
|__________|
Output: Node with value 2
Explanation: The tail connects to the node at index 1.
Input: head = [1, 2], pos = 0
1 -> 2
↑ |
|____|
Output: Node with value 1
Explanation: The tail connects to the head.
Input: head = [1], pos = -1
Output: null
Explanation: No cycle in the list.
Brute Force Approach (Using HashSet)
Intuition
As we traverse the linked list, we store each visited node in a hash set. The first node we encounter that's already in the set is the starting point of the cycle.
Algorithm
- Create a hash set to store visited nodes
- Traverse the linked list
- For each node:
- If it's in the set, return it (cycle start found)
- Otherwise, add it to the set
- If we reach null, return null (no cycle)
Implementation
Complexity Analysis
- Time Complexity: O(n) - Each node is visited at most once
- Space Complexity: O(n) - Hash set stores all nodes in worst case
Optimal Approach (Floyd's Algorithm)
Intuition
Floyd's algorithm can not only detect a cycle but also find its starting point. After the slow and fast pointers meet inside the cycle, if we reset one pointer to head and move both at the same speed, they will meet at the cycle's starting point.
Mathematical Proof
Let's define:
- m = distance from head to cycle start
- k = distance from cycle start to meeting point
- L = cycle length
When slow and fast meet:
- slow traveled: m + k
- fast traveled: m + k + nL (for some n >= 1)
Since fast travels twice as fast:
2(m + k) = m + k + nL
m + k = nL
m = nL - k
m = (n-1)L + (L - k)
This means: distance from head to cycle start equals
distance from meeting point to cycle start (going forward)
Algorithm
- Detect cycle using Floyd's algorithm
- If no cycle, return null
- Reset slow pointer to head
- Move both slow and fast one step at a time
- The point where they meet is the cycle start
Visualization
List: 1 -> 2 -> 3 -> 4 -> 5 -> 6
↑ |
|______________|
m = 2 (distance to cycle start, node 3)
L = 4 (cycle length: 3 -> 4 -> 5 -> 6 -> 3)
Phase 1: Detection
- slow and fast meet somewhere in the cycle
Phase 2: Find cycle start
- Reset slow to head (node 1)
- Move both one step at a time
- After m steps, both reach node 3 (cycle start)
Implementation
Complexity Analysis
- Time Complexity: O(n) - Both phases are O(n)
- Space Complexity: O(1) - Only using two pointers
Finding Cycle Length
As a bonus, we can also find the length of the cycle:
Key Takeaways
- Floyd's algorithm elegantly solves both cycle detection and finding cycle start
- The mathematical proof is based on the relationship:
m = nL - k - After detection, resetting one pointer to head and moving both at same speed leads to cycle start
- This is one of the most frequently asked linked list problems in interviews
- Understanding the proof helps in explaining the solution confidently
- The algorithm can be extended to find cycle length as well
- Time complexity is O(n) and space complexity is O(1) for the optimal solution