Aug 102012
 

Given a Singly linked list which may contain a loop (link of last node pointing to some Node in the list). Write code to detect the loop.

Traverse the list till the end (Incorrect Solution).

If there is a loop in the list, then there is no end, we never know when we have reached the repeating value (unless we are marking the nodes).

Detecting only Full Loop (Incomplete Solution).

Sometimes, The first approach is to traverse the list using a temporary pointer untill it becomes null or becomes equal to the head pointer.

If it becomes equal to head pointer, there is a loop. If it becomes NULL, there is no loop.

The Flaw in this approach is that it will only detect the loop if the last node is pointing to the first node. It will not detect intermediate loops (as shown in the picture above).

Brute-Force Method:

For each Node, traverse the entire list from the start till the previous Node and see if there is a Node which is equal to the current Node. If yes then we have detected a loop, else continue.

It is like checking the entire list we have traversed so far. This method will take O(n2) time.

Marking the visited Nodes

Marking can be done in two ways

1. Using hash table to store the Nodes which are visited.

Traversing the list. For each Node
If the Node is present in the Hash table 
    Loop detected
Else
    Store the Node in Hash Table and move forward

2. Keeping an extra field per node. Structure of the Node will be

        struct Node
        {
            int data;
            Node* link;
            bool visited;
        };

Initially all the nodes will visited=false.

Traversing the list. For each Node
If visited of the Node is true
    Loop detected
Else
    set node.visited=true and move forward

Both of these methods will require O(n) extra space.

Reversing the list

Don’t change pointer to the head Node. Reverse the list.

If there is a loop in the list you will reach the head node itself while reversing the list.

If you don’t reach the head Node there is no loop in the list.

This is an O(n) time algorithm and requires O(1) extra space. But you need to reverse the list twice, first to detect the loop and then to restore the original list. Hence the constant factor of time is large.

Using Two Pointers (Best Algorithm)

This is also called “Tortoise & Hare Algorithm“, In this algorithm we traverse the list simultaneously using a fast pointer and a slow pointer. If there is a loop the two will become equal:

1. take two pointers ptrSlow and ptrFast both pointing to head node
2. While (ptrSlow != ptrFast and ptrFast != NULL)
   - increment ptrSlow by one Node (ptrSlow = ptrSlow->link)
   - increment ptrFast by two Node (ptrFast = ptrFast->link->link)

Code:

    bool detectLoop(Node *head)
    {
        Node* slowPtr = head;
        Node* fastPtr = head;

        while(fastPtr != NULL && fastPtr->link != NULL )
        {
            slowPtr = slowPtr->link;
            fastPtr  = fastPtr->link->link;

            if (slowPtr == fastPtr)
                return true;
        }
        return false;
    }

Note: If it is a doubly linked list then one more solution can be to check backward (using previous pointer to see it this node is present in the already traversed list).

  13 Responses to “Detecting loop in a linked list”

Comments (13)
  1. Keep on working, great job!

  2. Very quickly this website will be famous among all blogging and site-building visitors, due to it’s nice content

  3. Fastidious respond in return of this issue with solid arguments and telling the whole thing on the topic of that.

 Leave a Reply

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

(required)

(required)