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.