Finding if a cycle exists in a Linked List

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:

p1 and p2 at same position
p1 moves 1 step while p2 moves 2 step
p1 moves 1 step and p2 moves 2 step
p1 moves 1 step and both p1, p2 are at same position

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.

Tirthankar Kundu

Tirthankar Kundu