⚡ TL;DR
Solve Linked List Cycle in Dart with working code. Floyd's Tortoise & Hare (Optimal) approach with O(n) time, plus complexity analysis and interview tips.
Linked List Cycle (#141 — Easy): Given head, the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if some node can be reached again by continuously following the next pointer.
Problem Statement
Given head, the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if some node can be reached again by continuously following the next pointer.
Example:
Input: head = [3,2,0,-4], pos = 1 (tail connects to node index 1)
Output: trueApproach: Floyd’s Tortoise & Hare (Optimal)
Time: O(n) | Space: O(1)
Two pointers at different speeds: fast moves 2 steps, slow moves 1. If there’s a cycle, fast will eventually lap slow and they’ll meet. O(1) space.
class ListNode {
int val;
ListNode? next;
ListNode(this.val);
}
bool hasCycle(ListNode? head) {
var slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow!.next;
fast = fast.next!.next;
if (identical(slow, fast)) return true;
}
return false;
}Approach: Hash Set
Time: O(n) | Space: O(n)
Store every visited node in a set. If we revisit a node, a cycle exists. Uses O(n) space but works even when you cannot modify the list.
bool hasCycleSet(ListNode? head) {
final seen = <ListNode>{};
var node = head;
while (node != null) {
if (seen.contains(node)) return true;
seen.add(node);
node = node.next;
}
return false;
}Key Takeaways
- Start with the brute-force approach to understand the problem
- Floyd’s Tortoise & Hare (Optimal) gives the optimal O(n) solution
- Practice this pattern — it appears frequently in coding interviews
Related Problems
- Linked List Cycle in Python
- Linked List Cycle in Go
- Linked List Cycle in Swift
- Remove Duplicates from Sorted Array in Dart
- Reverse Linked List in Dart
- Reverse String in Dart
FAQ
What is the best approach to solve Linked List Cycle in Dart?
The recommended approach is Floyd’s Tortoise & Hare (Optimal), which runs in O(n) time with O(1) space. The full Dart implementation is shown above.
What is the time complexity of Linked List Cycle in Dart?
Using Floyd’s Tortoise & Hare (Optimal), the time complexity is O(n) and the space complexity is O(1).
Happy coding!
