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.

Algorithm:

• 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.