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.