Floyd’s Cyclic Algorithm – DEV Community

This algorithm is used to find loops in a list.

The idea is if we leave two indicators on the same list. If there is no loop in the list, the quick loop will run to the end of the list or to None.

However, if there are any loops within the loop, the two indicators are bound to conflict with each other.

This will give us a true or False value if there are any loops in the listing.

To further understand where the loop starts, some math is required.

Given that we found the point where the two pointers intersected, we can start 2 more pointers, one starting from the point where the previous 2 pointers intersected and the other starting from the beginning of the list, following the some math attached in the picture to calculate next these two The pointers are bound to meet at the beginning of the loop.

One problem that can be solved using this algorithm is the problem

141. Linked list loop

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:

        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True

        return False

Feel free to point out any errors or any additions 🙂