Language Selection
Choose your preferred programming language
Showing: Python
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. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.
Notice that you should not modify the linked list.
Input/Output Specifications
- Input: Head of a linked list
- Output: Node where the cycle begins, or null if no cycle
- Constraints:
- The number of the nodes in the list is in the range [0, 10^4]
- -10^5 <= Node.val <= 10^5
- pos is -1 or a valid index in the linked-list
Examples
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the 1st node (0-indexed).
Example 2:
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the 0th node.
Example 3:
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.
Solutions
Approach 1: Floyd’s Cycle Detection (Two Phases)
This approach uses Floyd’s cycle detection algorithm in two phases: first to detect the cycle, then to find the starting point.
Algorithm:
- Phase 1: Use slow and fast pointers to detect if there’s a cycle
- If no cycle is detected, return null
- Phase 2: Reset one pointer to head and move both pointers one step at a time
- The meeting point is the start of the cycle
Python:
def detectCycle(head):
"""
Detect cycle and find the starting point using Floyd's algorithm
Time: O(n)
Space: O(1)
"""
if not head or not head.next:
return None
# Phase 1: Detect cycle
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None # No cycle found
# Phase 2: Find the starting point
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
Java:
class Solution {
/**
* Detect cycle and find the starting point using Floyd's algorithm
* Time: O(n)
* Space: O(1)
*/
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
// Phase 1: Detect cycle
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
if (fast == null || fast.next == null) {
return null; // No cycle found
}
// Phase 2: Find the starting point
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
Go:
// detectCycle - Detect cycle and find the starting point using Floyd's algorithm
// Time: O(n)
// Space: O(1)
func detectCycle(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return nil
}
// Phase 1: Detect cycle
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
break
}
}
if fast == nil || fast.Next == nil {
return nil // No cycle found
}
// Phase 2: Find the starting point
slow = head
for slow != fast {
slow = slow.Next
fast = fast.Next
}
return slow
}
JavaScript:
/**
* Detect cycle and find the starting point using Floyd's algorithm
* Time: O(n)
* Space: O(1)
*/
function detectCycle(head) {
if (head === null || head.next === null) {
return null;
}
// Phase 1: Detect cycle
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
break;
}
}
if (fast === null || fast.next === null) {
return null; // No cycle found
}
// Phase 2: Find the starting point
slow = head;
while (slow !== fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
C#:
public class Solution {
/// <summary>
/// Detect cycle and find the starting point using Floyd's algorithm
/// Time: O(n)
/// Space: O(1)
/// </summary>
public ListNode DetectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
// Phase 1: Detect cycle
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
if (fast == null || fast.next == null) {
return null; // No cycle found
}
// Phase 2: Find the starting point
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
Approach 2: Hash Set (Extra Space)
This approach uses a hash set to keep track of visited nodes.
Algorithm:
- Traverse the linked list
- For each node, check if it’s already in the hash set
- If yes, return that node (cycle start)
- If no, add the node to the hash set and continue
- If we reach the end, return null
Python:
def detectCycleHashSet(head):
"""
Detect cycle using hash set
Time: O(n)
Space: O(n)
"""
visited = set()
current = head
while current:
if current in visited:
return current
visited.add(current)
current = current.next
return None
Java:
class Solution {
/**
* Detect cycle using hash set
* Time: O(n)
* Space: O(n)
*/
public ListNode detectCycleHashSet(ListNode head) {
Set<ListNode> visited = new HashSet<>();
ListNode current = head;
while (current != null) {
if (visited.contains(current)) {
return current;
}
visited.add(current);
current = current.next;
}
return null;
}
}
Go:
// detectCycleHashSet - Detect cycle using hash set
// Time: O(n)
// Space: O(n)
func detectCycleHashSet(head *ListNode) *ListNode {
visited := make(map[*ListNode]bool)
current := head
for current != nil {
if visited[current] {
return current
}
visited[current] = true
current = current.Next
}
return nil
}
JavaScript:
/**
* Detect cycle using hash set
* Time: O(n)
* Space: O(n)
*/
function detectCycleHashSet(head) {
const visited = new Set();
let current = head;
while (current !== null) {
if (visited.has(current)) {
return current;
}
visited.add(current);
current = current.next;
}
return null;
}
C#:
public class Solution {
/// <summary>
/// Detect cycle using hash set
/// Time: O(n)
/// Space: O(n)
/// </summary>
public ListNode DetectCycleHashSet(ListNode head) {
HashSet<ListNode> visited = new HashSet<ListNode>();
ListNode current = head;
while (current != null) {
if (visited.Contains(current)) {
return current;
}
visited.Add(current);
current = current.next;
}
return null;
}
}
Key Insights
- Floyd’s algorithm: Two-phase approach to detect cycle and find start point
- Mathematical proof: The distance from head to cycle start equals the distance from meeting point to cycle start
- Space optimization: Floyd’s algorithm uses O(1) space vs O(n) for hash set
- Cycle detection: The meeting point indicates a cycle exists
- Start point finding: Reset one pointer to head and move both one step at a time
Edge Cases
- Empty list
- Single node list (no cycle possible)
- Single node pointing to itself (cycle)
- Cycle at the head
- Cycle at the tail
- Very long lists with cycles
Test Cases
# Test case 1: Cycle exists
head1 = ListNode(3)
head1.next = ListNode(2)
head1.next.next = ListNode(0)
head1.next.next.next = ListNode(-4)
head1.next.next.next.next = head1.next # Creates cycle
# Expected: Node with value 2
# Test case 2: No cycle
head2 = ListNode(1)
head2.next = ListNode(2)
head2.next.next = ListNode(3)
# Expected: None
# Test case 3: Single node cycle
head3 = ListNode(1)
head3.next = head3 # Points to itself
# Expected: Node with value 1
# Test case 4: Cycle at head
head4 = ListNode(1)
head4.next = ListNode(2)
head4.next.next = head4 # Points back to head
# Expected: Node with value 1
Follow-up Questions
- How would you handle very large lists?
- Can you solve this with O(1) space and O(1) time?
- How would you break a cycle in a linked list?
- What if the list has multiple cycles?
Common Mistakes
- Not handling the case where no cycle exists
- Incorrect pointer movement in the second phase
- Not properly resetting the slow pointer to head
- Forgetting to check if fast pointer reaches the end
- Off-by-one errors in pointer movement
- Memory issues with hash set approach for very large lists