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