Saturday, January 29, 2011

How to detect a loop in a single linked list

Continue my topic regarding linked list, I couple days ago , after I create the linked list class, I was thinking , in a single list, if one node point to a node prior to itself in the list, then it create a loop.  Then when you traverse the linked list, Ooops! you get into a dead loop.
So I was thinking How to detect this loop situation, then I did some research over internet, I do find quite a lot good articles.  here is one,  http://ostermiller.org/find_loop_singly_linked_list.html it explain good solutions and bad solutions.
this is another one explain how to address the culprit which cause the loop http://crackinterviewtoday.wordpress.com/2010/03/16/calculate-node-that-causes-loop-in-a-linked-list/

Today,I get some time , so I implement the function , here is the code.
Not only this function can address the loop, but also , it can address the exact node that cause it.


public bool hasLoop()
        {
            bool bReturn = false;
            
            if(_root != null && _root.next != null)
            {
                Node slow = _root;
                Node fast1 = Root;
                Node fast2 = Root;
                while(slow != null)
                {
                    fast1 = fast2.next;
                    if(fast1 != null)
                    {
                        fast2 = fast1.next;
                        if(fast1 == slow || fast2 == slow) //we have a loop
                        {
                            bReturn = true;
                            break;
                        }
                        else if(fast2 == null)//fast2 reach the end of linked list.
                        {
                            break;
                        }
                    }
                    else //fast1 is null means we reach the end of the linked list.
                    { 
                        break;
                    }
                    slow = slow.next;
                }
                slow = slow.next;
                Console.WriteLine(string.Format("Node:{0} cause a loop...",slow.Name));
            }
            
            return bReturn;
        }

No comments:

Post a Comment