Detect Cycle in Linked List

Detect if a linked list has a cycle using Floyd's cycle detection algorithm

Language Selection

Choose your preferred programming language

Showing: Python

Problem Statement

Given head, the head of a linked list, determine if the linked list has a cycle in it.

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.

Return true if there is a cycle in the linked list. Otherwise, return false.

Input/Output Specifications

Input: Head of a linked list
Output: Boolean indicating if cycle exists
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: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Solutions

Approach 1: Floyd’s Cycle Detection (Two Pointers)

This approach uses Floyd’s cycle detection algorithm, also known as the “tortoise and hare” algorithm. We use two pointers moving at different speeds - if there’s a cycle, the fast pointer will eventually catch up to the slow pointer.

Algorithm:

Initialize two pointers: slow and fast both pointing to head
Move slow one step at a time and fast two steps at a time
If there’s a cycle, fast will eventually meet slow
If fast reaches the end (null), there’s no cycle

Python:

def hasCycle(head):
    """
    Detect cycle in linked list using Floyd's cycle detection
    Time: O(n)
    Space: O(1)
    """
    if not head or not head.next:
        return False
    
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True
    
    return False

Java:

class Solution {
    /**
     * Detect cycle in linked list using Floyd's cycle detection
     * Time: O(n)
     * Space: O(1)
     */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                return true;
            }
        }
        
        return false;
    }
}

Go:

// hasCycle - Detect cycle in linked list using Floyd's cycle detection
// Time: O(n)
// Space: O(1)
func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
    
    slow := head
    fast := head
    
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        
        if slow == fast {
            return true
        }
    }
    
    return false
}

JavaScript:

/**
 * Detect cycle in linked list using Floyd's cycle detection
 * Time: O(n)
 * Space: O(1)
 */
function hasCycle(head) {
    if (head === null || head.next === null) {
        return false;
    }
    
    let slow = head;
    let fast = head;
    
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow === fast) {
            return true;
        }
    }
    
    return false;
}

C#:

public class Solution {
    /// <summary>
    /// Detect cycle in linked list using Floyd's cycle detection
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public bool HasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                return true;
            }
        }
        
        return false;
    }
}

Approach 2: Hash Set (Extra Space)

This approach uses a hash set to keep track of visited nodes. If we encounter a node that’s already in the set, there’s a cycle.

Algorithm:

Initialize a hash set to store visited nodes
Traverse the linked list
For each node, check if it’s already in the set
If yes, return true (cycle detected)
If no, add the node to the set and continue
If we reach the end, return false

Python:

def hasCycleHashSet(head):
    """
    Detect cycle using hash set
    Time: O(n)
    Space: O(n)
    """
    visited = set()
    current = head
    
    while current:
        if current in visited:
            return True
        visited.add(current)
        current = current.next
    
    return False

Java:

class Solution {
    /**
     * Detect cycle using hash set
     * Time: O(n)
     * Space: O(n)
     */
    public boolean hasCycleHashSet(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        ListNode current = head;
        
        while (current != null) {
            if (visited.contains(current)) {
                return true;
            }
            visited.add(current);
            current = current.next;
        }
        
        return false;
    }
}

Go:

// hasCycleHashSet - Detect cycle using hash set
// Time: O(n)
// Space: O(n)
func hasCycleHashSet(head *ListNode) bool {
    visited := make(map[*ListNode]bool)
    current := head
    
    for current != nil {
        if visited[current] {
            return true
        }
        visited[current] = true
        current = current.Next
    }
    
    return false
}

JavaScript:

/**
 * Detect cycle using hash set
 * Time: O(n)
 * Space: O(n)
 */
function hasCycleHashSet(head) {
    const visited = new Set();
    let current = head;
    
    while (current !== null) {
        if (visited.has(current)) {
            return true;
        }
        visited.add(current);
        current = current.next;
    }
    
    return false;
}

C#:

public class Solution {
    /// <summary>
    /// Detect cycle using hash set
    /// Time: O(n)
    /// Space: O(n)
    /// </summary>
    public bool HasCycleHashSet(ListNode head) {
        HashSet<ListNode> visited = new HashSet<ListNode>();
        ListNode current = head;
        
        while (current != null) {
            if (visited.Contains(current)) {
                return true;
            }
            visited.Add(current);
            current = current.next;
        }
        
        return false;
    }
}

Key Insights

Floyd’s algorithm: Uses two pointers moving at different speeds to detect cycles
Mathematical proof: If there’s a cycle, the fast pointer will eventually catch the slow pointer
Space optimization: Floyd’s algorithm uses O(1) space vs O(n) for hash set approach
Cycle detection: The meeting point indicates a cycle exists, but doesn’t tell us where the cycle starts

Edge Cases

Empty list (head is null)
Single node list (no cycle possible)
Single node pointing to itself (cycle)
Very long lists with cycles
Lists with cycles at different positions

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: True

# Test case 2: No cycle
head2 = ListNode(1)
head2.next = ListNode(2)
head2.next.next = ListNode(3)
# Expected: False

# Test case 3: Single node cycle
head3 = ListNode(1)
head3.next = head3  # Points to itself
# Expected: True

# Test case 4: Empty list
head4 = None
# Expected: False

Follow-up Questions

How would you find the starting point of the cycle?
Can you detect cycles in a doubly linked list?
How would you break a cycle in a linked list?
What’s the time complexity if the cycle is very long?

Common Mistakes

Not handling the empty list case
Incorrect pointer movement (forgetting to check fast.next)
Using wrong comparison operators (== vs !=)
Not initializing pointers correctly
Infinite loops when there’s no cycle but pointers aren’t moved properly
Memory issues with hash set approach for very large lists