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
- Move the pointer
slow_ptrby 1 and
- 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.
INPUT: Pointer to a linked list say
true if linked list contains loop else return
DATA STRUCTURE: A singly linked list.
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
Time complexity: O(n). Only one traversal of the loop is needed.
Auxiliary Space: O(1). There is no space required.
Hope you understand this algorithm. Let's solve some problem using this algorithm. click here