Detect cycle in linked list

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

The above is the detailed content of Detect cycle in linked list. For more information, please follow other related articles on the PHP Chinese website!