We've looked at using linear search to find a node in a linked list, inserting nodes in linked list to maintain a sorted list of values, and even created Stack and Queue abstract data structures using linked list as the underlying data structure. Now let's turn our attention to a very popular programming challenge using linked lists - detecting a cycle in a linked list.

Floyd's Cycle-Finding Algorithm

One popular algorithm for detecting cycles in linked lists is Floyd's Cycle-Finding Algorithm, which is often called the tortoise and the hare algorithm. The algorithm uses 2 pointers, a fast pointer and a slow pointer. The fast pointer ( hare ) traverses the linked list 2 nodes at a time while the slow pointer ( tortoise ) traverses the linked list 1 node at a time. If these pointers ever point to the same node in the linked, there is a cycle in the linked list.

Let's code Floyd's Cycle-Finding Algorithm in Python. We will use the same Node Class that represents a node in the linked list. It will hold an integer as its value and a pointer to None or the next node in the linked list.

class Node(object):
    def __init__(self, value: int, next_node: "Node" = None):
        self.value = value
        self.next = next_node

    def __repr__(self):
        return "Node <{}>".format(self.value)

Now let's write a Python function that will implement Floyd's Cycle-Finding Algorithm. We will create both a slow and fast pointer and both pointers will initially point to the head of the linked list. In a loop, we will increment the slow pointer by 1 and the fast pointer by 2. We then compare the pointers to see if they are pointing to the same node. If they are, there is a cycle in the linked list and we return True. If the pointers are never pointing to the same node and we have reached the end of the linked list, we return False.

Here is Python Function implementing Floyd's Cycle-Finding Algorithm.

def has_cycle(head: Node) -> bool:
    """Floyd's Cycle-Finding Algorithm"""

    slow, fast = head, head

    while fast is not None and fast.next is not None:
        slow, fast = slow.next, fast.next.next

        if slow == fast:
            return True

    return False

We can run Python test code to verify the function behaves accordingly. First, let's create a linked list that does not have a cycle and verify the function returns False.

linked_list = Node(1, Node(2, Node(3, Node(4))))

assert not has_cycle(linked_list)

Now let's create a linked list where the last node in the list connects to the first node. Floyd's Cycle-Finding Algorithm should detect the cycle and the function should return True.

node4 = Node(4)
linked_list = Node(1, Node(2, Node(3, node4)))
node4.next = linked_list

assert has_cycle(linked_list)

Conclusion

Detecting a cycle in a linked list is a popular technical interview question and Floyd's Cycle-Finding Algorithm is a popular solution.

Posted by David Hayden

David Hayden is a freelance web developer. In his spare time he tutors students on a wide variety of computer science topics and programming languages. You can find him on twitter as @koderdojo.

Related Posts: