3

Floyd’s Cycle Detection Algorithm

 2 years ago
source link: https://dev.to/suvasish114/floyds-cycle-detection-algorithm-7cm
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

The purpose is to determine whether the linked list has a cycle or not. This is the fastest method to find cycle in a linked list. The terminology of this algorithm is-

  • Traverse linked list using two pointers named slow_ptr and fast_ptr.
  • Move the pointer slow_ptr by 1 and fast_ptr by 2.
  • If these pointers meet at the same node then there is a loop. If pointers do not meet then linked list doesn’t have a loop.

Algorithm

INPUT: Pointer to a linked list say HEAD.

OUTPUT: Return true if linked list contains loop else return false.

DATA STRUCTURE: A singly linked list.

STEPS:

    If(HEAD == NULL || HEAD->link == NULL) then
        Return false
        Exit
    Else
        // initializing staring pointers
        fast_ptr = HEAD
        slow_ptr = HEAD
        While(HEAD != NULL) do
            // move slow_ptr by 1 step and fast_ptr by 2 steps
            slow_ptr = slow_ptr->link;
            fast_ptr = fast_ptr->link->link;
            If(slow_ptr == fast_ptr)then
                Return true
            EndIf
            HEAD = HEAD->link
        EndWhile
        Return false
    EndIf
Enter fullscreen modeExit fullscreen mode

Complexity

Time complexity: O(n). Only one traversal of the loop is needed.

Auxiliary Space: O(1). There is no space required.

References

codingninjas.com, geeksforgeeks.org

Conclusion

Hope you understand this algorithm. Let's solve some problem using this algorithm. click here


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK