tick90-linklist-1784911768
The solution implements Floyd's cycle-finding algorithm (tortoise and hare) with two pointers: slow moves one step at a time, fast moves two steps. If there's a cycle, the fast pointer will eventually lap the slow pointer and they'll meet. If either reaches nil, the list is acyclic.
Type definition and function:
// ListNode defines a node in a singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
// hasCycle uses Floyd's cycle-finding algorithm (tortoise and hare)
// to determine if a singly-linked list has a cycle.
// Returns true if a cycle exists, false otherwise.
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
}
Key details:
- Early exit for nil and single-node lists (no cycle possible).
- Both pointers start at head. This is valid because the loop condition fast != nil && fast.Next != nil ensures we never dereference a nil pointer.
- Time complexity: O(n) — the hare traverses the list at most twice.
- Space complexity: O(1) — only two pointer variables.
All 7 tests passed successfully: | # | Case | Result | Expected | |---|------|--------|----------| | 1 | `nil` head | `false` | `false` | | 2 | Single node (no cycle) | `false` | `false` | | 3 | Linear list of 3 nodes | `false` | `false` | | 4 | Cycle back to head (3 nodes) | `true` | `true` | | 5 | Cycle back to middle (4 nodes) | `true` | `true` | | 6 | Two nodes, no cycle | `false` | `false` | | 7 | Two nodes, tail → head cycle | `true` | `true` | **Edge cases covered:** - **Empty list** — `nil` head returns `false`. - **Single node** — no cycle possible, returns `false`. - **Two nodes** — both acyclic and cyclic configurations tested. - **Longer acyclic list** — linear chain of 3 nodes. - **Cycle at head** — tail points back to first node. - **Cycle at middle** — tail points to an interior node. ---
{"model": "gpt-4o", "problem_class": "tick90-linklist-1784911768", "result": "passed", "tests": 7}