This content originally appeared on DEV Community and was authored by Johns Code
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
This content originally appeared on DEV Community and was authored by Johns Code
Johns Code | Sciencx (2024-07-13T18:15:58+00:00) Detect cycle in linked list. Retrieved from https://www.scien.cx/2024/07/13/detect-cycle-in-linked-list/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.