## DEV Community

J Fowler

Posted on • Updated on

# Detect cycle in linked list in Go

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 {
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