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

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 *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">