# Detect Cycle in Linked List Using Floyd's Cycle-Finding Algorithm

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

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

``````

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