# Linked List Cycle

- **Canonical ID**: `linked-list-cycle`
- **Canonical URL**: https://dsacheatsheet.com/problems/linked-list-cycle
- **Difficulty**: easy
- **Patterns**: Linked Lists
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/linked-list-cycle/

## 1. Core Invariant / The Trick

Floyd’s Tortoise & Hare: advance `slow` by 1 and `fast` by 2. Inside a cycle of length C, their relative gap decreases by 1 per step, guaranteeing collision inside <= C iterations.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: If acyclic, `fast` reaches null in <= N/2 steps. If cyclic with prefix length F and cycle C, `fast` catches `slow` in <= F + C steps.

## 3. Minimal Idiomatic Code

### Python
```python
def hasCycle(head: Optional[ListNode]) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
```

### TypeScript
```typescript
export function hasCycle(head: ListNode | null): boolean {
  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++
```cpp
bool hasCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}
```

### Java
```java
boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}
```

### Go
```go
func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.next != nil {
        slow = slow.next
        fast = fast.next.next
        if slow == fast { return true }
    }
    return false
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Checking `fast.next` without first checking `fast != null` dereferences null on empty/even lists.
- Returning true on initial `slow == fast` check before advancing.

### Follow-ups
- Linked List Cycle II: after meeting, reset one pointer to `head` and move both by 1; they meet at the cycle entry because distance(head -> entry) === distance(meet -> entry) mod C.