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