Skip to content
The Chat Archive
claude-sonnet-4-20250514-thinking-32k· Anthropic LMArena Human Preference 140K

Design a function that checks if a singly linked list contains a cycle.

  1. User

    Design a function that checks if a singly linked list contains a cycle.

  2. Assistant

    Here's a function to detect cycles in a singly linked list using Floyd's Cycle Detection Algorithm (also known as the "tortoise and hare" approach):

    class ListNode:
        def __init__(self, val=0, next=None):
            self.val = val
            self.next = next
    
    def has_cycle(head):
        """
        Detects if a singly linked list contains a cycle.
        
        Args:
            head: The head node of the linked list
            
        Returns:
            bool: True if cycle exists, False otherwise
        """
        if not head or not head.next:
            return False
        
        # Initialize two pointers
        slow = head  # moves one step at a time
        fast = head  # moves two steps at a time
        
        # Traverse the list
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            # If pointers meet, there's a cycle
            if slow == fast:
                return True
        
        # If we reach here, no cycle exists
        return False
    

    Here's how it works:

    Algorithm Logic:

    • Use two pointers moving at different speeds
    • If there's no cycle, the fast pointer reaches the end first
    • If there's a cycle, the fast pointer will eventually "lap" the slow pointer

    Time Complexity: O(n) where n is the number of nodes Space Complexity: O(1) - only uses two pointer variables

    Example usage:

    # Create a list with cycle: 1 -> 2 -> 3 -> 4 -> 2 (cycle back to node 2)
    node1 = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node4 = ListNode(4)
    
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node2  # Creates cycle
    
    print(has_cycle(node1))  # Output: True
    
    # Create a list without cycle: 1 -> 2 -> 3 -> None
    node5 = ListNode(1)
    node6 = ListNode(2)
    node7 = ListNode(3)
    
    node5.next = node6
    node6.next = node7
    
    print(has_cycle(node5))  # Output: False
    

    The algorithm is elegant because it guarantees that if a cycle exists, the two pointers will eventually meet inside the cycle, similar to how a faster runner on a circular track will eventually lap a slower runner.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.