Floyd’s Cyclic Algorithm

This algorithm is used to find cycles in lists.

The Idea is if we leave two pointers on the same list. if there are no loops in the list the fast loop will run into the end of the list or run into None.

But if there are any loops present in the loop the two pointers are bound to run into each other.

this will give us a truth or False value if there exists any loops in the list.

To take it a step further to see where the loop starts there is some math involved.

Given that we find the point where both the pointers meet, we can start 2 more pointer one will start from the point where the previous 2 pointers met and the other one starts at the beginning of the list and as per some maths attached in the picture next these 2 pointers are bound to meet at the beginning of the loop.

One question you can solve using this algorithm is problem

141. Linked List Cycle

# 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 drop in any mistakes or any additions :)