claude-sonnet-4-20250514-thinking-32k· Anthropic LMArena Human Preference 140K
Design a function that checks if a singly linked list contains a cycle.
- User
Design a function that checks if a singly linked list contains a cycle.
- 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 FalseHere'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: FalseThe 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.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.