What is Linked List?
A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:
Thus, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.
Now, we say a Linked List consists of cycle if one of the node points back to some other node forming a cycle like below:
Now, we need to come up with an algorithm where we need to detect if a cycle exists in the Linked List or not.
- Traverse linked list using two pointers
- Move one pointer(p1) by one and another pointer(p2) by two
- If these pointers (p1, p2) meet at the same node then there is a loop
- If pointers do not meet then linked list doesn’t have a loop
Let's visually see the process:
This shows that we were able to detect the cycle using this simple algorithm.
This is also known as Floyd's cycle detection algorithm.
Let's end this with a small python code implementation:
def containsCycle(self, head: ListNode) -> bool: p1 = head p2 = head while(p1 and p2 and p1.next): p1 = p1.next p2 = p2.next.next if p1 == p2: return True return False
Hope you liked it! Cheers.