Another linked list algorithm.
Detect a cycle in a linked list.
This is actually not that bad. There are at least 3 different ways to do it O(n) time.
The easiest way requires modifying the linked list node to include a flag that denotes if a node has been visited. As the list is traversed, if we encounter a node that has been visited then there is a cycle.
Another technique uses a hashmap containing visited nodes or references to them. As the list is traversed nodes, or their references, are inserted into the hash. If we encounter a node that is already represented in the hashmap, then a cycle exists. While this technique only requires a single traversal, it does require more memory due to the hashmap.
For this post, I am going to use Floyd's algorithm to detect the cycle. It's pretty simple.
func DetectCycle[T any](ll *LinkedList[T]) bool {
slow := ll.Head
fast := ll.Head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if fast == slow {
return true
}
}
return false
}
This technique uses 2 pointers into the list. As the list is traversed, one pointer moves one node at a time and the other moves two nodes at a time. If the 2 pointers ever meet, a cycle exists.
Why does this work? As the list is traversed, the distance between the two pointers increases. If there is a cycle, the fast pointer will 'lap' the slow one.
Is there a more efficient implementation? Are any boundary conditions missing? Let me know in the comments.
Thanks!
The code for this post and all posts in this series can be found here