Detect a loop in a Linked List

Suppose you are given a linked list like this:

linked-list-loop

And you want to remove the loop in it.

A very trivial way can be storing a boolean “visited” variable which stores true or false depending on whether a node is visited or not. But we need to store this info in each and every node. This will cost us some space.

A very clever way is to use two pointer for traversing the linked list. one pointer will travel one node at a time and other node will travel two nodes at a time. we can also call the pointers as slowpointer and fastpointer. Now, if there is a loop in a linked list , these two pointers will meet at a certain node.

The above mentioned algorithm was proposed by Robert Floyd and is also called Floyd’s loop detection algorithm.

so, this is how we detect a loop in a Linked List.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s