Floyd’s Cycle Detection Algorithm

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 poi…


This content originally appeared on DEV Community and was authored by Suvasish Das

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

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


This content originally appeared on DEV Community and was authored by Suvasish Das


Print Share Comment Cite Upload Translate Updates
APA

Suvasish Das | Sciencx (2021-10-24T13:28:15+00:00) Floyd’s Cycle Detection Algorithm. Retrieved from https://www.scien.cx/2021/10/24/floyds-cycle-detection-algorithm-2/

MLA
" » Floyd’s Cycle Detection Algorithm." Suvasish Das | Sciencx - Sunday October 24, 2021, https://www.scien.cx/2021/10/24/floyds-cycle-detection-algorithm-2/
HARVARD
Suvasish Das | Sciencx Sunday October 24, 2021 » Floyd’s Cycle Detection Algorithm., viewed ,<https://www.scien.cx/2021/10/24/floyds-cycle-detection-algorithm-2/>
VANCOUVER
Suvasish Das | Sciencx - » Floyd’s Cycle Detection Algorithm. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2021/10/24/floyds-cycle-detection-algorithm-2/
CHICAGO
" » Floyd’s Cycle Detection Algorithm." Suvasish Das | Sciencx - Accessed . https://www.scien.cx/2021/10/24/floyds-cycle-detection-algorithm-2/
IEEE
" » Floyd’s Cycle Detection Algorithm." Suvasish Das | Sciencx [Online]. Available: https://www.scien.cx/2021/10/24/floyds-cycle-detection-algorithm-2/. [Accessed: ]
rf:citation
» Floyd’s Cycle Detection Algorithm | Suvasish Das | Sciencx | https://www.scien.cx/2021/10/24/floyds-cycle-detection-algorithm-2/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts