How to find/detect infinite loop of linked list in java

There are multiple solutions to solve this. But we will discuss Floyd’s Cycle-Finding Algorithm.

This algorithm also called as “Tortoise and Hare Algorithm”.

Solution:

1)      Initialize 2 pointers called fast and slow with header element. Move slow pointer by one element and fast pointer by two elements

2)      If these 2 pointers meet at some node then there is loop.

It’s very easy to find. Let’s see the example.

 Output:

 

See below screen shot, here there is an infinite loop exits.

1–>2–>3–>4–>2–>3–>4–>2–>3–>4–>2… continues. No ending. This is called infinite loop/cycle in linked list.

LinkedListLoop

Posted in data-structures and tagged , , .

Leave a Reply

Your email address will not be published. Required fields are marked *