Write a program to Detect loop in a linked list
Detect Loop in a Linked List - Floyd's Cycle Detection
Problem Statement
Given head, the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if some node in the list can be reached again by continuously following the next pointer.
Return true if there is a cycle in the linked list, otherwise return false.
Example
Input: head = [3, 2, 0, -4], pos = 1 (tail connects to node at index 1)
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the second node.
Input: head = [1, 2], pos = 0 (tail connects to node at index 0)
Output: true
Input: head = [1], pos = -1 (no cycle)
Output: false
Brute Force Approach (Using HashSet)
Intuition
As we traverse the linked list, we can store each visited node in a hash set. If we encounter a node that's already in the set, we've found a cycle. If we reach the end (null), there's no cycle.
Algorithm
- Create a hash set to store visited nodes
- Traverse the linked list
- For each node, check if it exists in the set
- If yes, return true (cycle detected)
- If no, add the node to the set
- If we reach null, return false (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 Cycle Detection)
Intuition
Floyd's Cycle Detection algorithm uses two pointers moving at different speeds (slow and fast, also known as Tortoise and Hare). If there's a cycle, the fast pointer will eventually catch up to the slow pointer inside the cycle.
Why does this work?
- In each iteration, the fast pointer gains 1 step on the slow pointer
- If there's a cycle of length L, after the slow pointer enters the cycle, the fast pointer will catch up in at most L steps
- If there's no cycle, the fast pointer will reach the end
Algorithm
- Initialize two pointers: slow and fast, both starting at head
- Move slow by 1 step and fast by 2 steps in each iteration
- If fast reaches null or fast.next is null, no cycle exists
- If slow and fast meet, a cycle exists
Visualization
List with cycle: 1 -> 2 -> 3 -> 4 -> 5
↑ |
|_________|
Step 0: slow = 1, fast = 1
Step 1: slow = 2, fast = 3
Step 2: slow = 3, fast = 5
Step 3: slow = 4, fast = 4 ← They meet! Cycle detected
List without cycle: 1 -> 2 -> 3 -> 4 -> 5 -> null
Step 0: slow = 1, fast = 1
Step 1: slow = 2, fast = 3
Step 2: slow = 3, fast = 5
Step 3: slow = 4, fast = null ← Fast reached end, no cycle
Implementation
Complexity Analysis
- Time Complexity: O(n) - At most O(n + k) where k is the cycle length
- Space Complexity: O(1) - Only using two pointers
Mathematical Proof of Floyd's Algorithm
Let's prove why the slow and fast pointers will meet:
- Let the distance from head to cycle start be
m - Let the cycle length be
k - When slow pointer enters the cycle, it has traveled
msteps - At this point, fast pointer has traveled
2msteps - Fast pointer is
(2m - m) mod k = m mod ksteps ahead of slow in the cycle - In each step, fast gains 1 on slow
- They will meet after
k - (m mod k)more steps
This guarantees they will meet within the cycle.
Key Takeaways
- Floyd's Cycle Detection is a classic algorithm using slow and fast pointers
- Also known as Tortoise and Hare algorithm
- The optimal solution uses O(1) space vs O(n) for hash set approach
- This algorithm is foundational for other cycle problems:
- Finding the starting point of the cycle
- Finding the length of the cycle
- Detecting cycles in other data structures
- Always check edge cases: empty list, single node, two nodes
- The algorithm is guaranteed to find the cycle if one exists