How to find whether a linked list is a circular linked list
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 14 of 14

Thread: How to find whether a linked list is a circular linked list

  1. #1
    Join Date
    Sep 2008
    Posts
    48

    How to find whether a linked list is a circular linked list

    Hi,
    Can anyone provide some algorithm to find whether a linked list is circular or not ? provide the algorithm should not used normal linear search.

    Thanks

  2. #2
    Join Date
    Oct 2006
    Posts
    616

    Re: How to find whether a linked list is a circular linked list

    QUOTE=rsodimbakam]provide the algorithm should not used normal linear search.[/QUOTE]

    I'm not sure what is "normal linear search", but a typical method of finding if a linked list is circular is:
    Code:
    bool IsCircular(Node* head)
    {
          bool circleFound = false;
          bool tailFound = false;
    
          if (head && head->next)
         {
              Node* slower = head;
              Node* faster = head;
    
              do 
              {
                   slower = slower->next;
                   faster =  faster->next->next;
                   tailFound = ! (faster && faster->next);
                   if ( ! tailFound )
                   {
                       circleFound = (slower == faster || slower == faster->next);                                         
                   }
              }
              while ( ! tailFound && ! circleFound)
         }
    
         return ( circleFound );
    }
    Regards,
    Zachm

  3. #3
    Join Date
    Feb 2008
    Posts
    966

    Re: How to find whether a linked list is a circular linked list

    Wow...Zachm just wow (jumping two spots instead of one still makes it linear...).

    Unless the list is a doubly linked list (forward and backward references) you don't have a choice but to do a linear search down the list until you reach the end. That's the whole point of a linked list: they are linked, one by one...

    The only way to do it on a singularly linked list is to linearly traverse to the last object and see whether or not it has a reference to the "head" object. If it does, great, otherwise it should point to null.

    If you have a doubly linked list then you can simply check head->previous.

  4. #4

    Re: How to find whether a linked list is a circular linked list

    Quote Originally Posted by ProgramThis
    The only way to do it on a singularly linked list is to linearly traverse to the last object and see whether or not it has a reference to the "head" object. If it does, great, otherwise it should point to null.
    The standard way of solving it for a singly linked list was posted by Zachm. This covers cases where the list is a 6 rather than an O - it is circular (ie if you iterate over it you won't reach the end), but the head isn't in the ring.

    Performing a linear scan for the head only will detect an O-list, and will fail in a infinite loop for a 6-list.

    Other techniques, such putting all visited nodes into a hash set are rarely better in running time and are more costly in space.

    People of a non-concurrent low-level bias might also mark the least significant bit of the pointer to indicate the pass, but since you have to visit each node again to remove the mark, this still requires 2N operations, and writes often cost more than reads.

  5. #5
    Join Date
    Feb 2008
    Posts
    966

    Re: How to find whether a linked list is a circular linked list

    Quote Originally Posted by pm_kirkham
    The standard way of solving it for a singly linked list was posted by Zachm. This covers cases where the list is a 6 rather than an O - it is circular (ie if you iterate over it you won't reach the end), but the head isn't in the ring.
    First off, if you have a dummy header pass the search method head->next, then you are doing exactly what I have recommended.

    to find whether a linked list is circular or not
    The OP asked to find whether the list is circular or not, not whether or not it had cycles. The code posted above will only tell if there are cycles, not circular (which is what the OP needs). So if the list is cyclic (your '6') then your code will come back and say "yes, the tail directly links to the first element that is not a dummy header (circular list)" which is incorrect.

  6. #6

    Re: How to find whether a linked list is a circular linked list

    Quote Originally Posted by ProgramThis
    First off, if you have a dummy header pass the search method head->next, then you are doing exactly what I have recommended.
    If you perform a linear scan for a fixed pointer on a 6 shaped circular list then the procedure will not terminate.

    Specifically, with the circular list:

    node_1 -> node_2 -> node_3 -> node_4 -> node_2

    an attempt to follow the procedure given will fail:
    traverse to the last object and see whether or not it has a reference to the "head" object. If it does, great, otherwise it should point to null.
    The procedure doesn't detect that node_4 is the last - it has neither a reference to null or to node_1, the head.

    The algorithm with the slow and fast will terminate in that case.
    The OP asked to find whether the list is circular or not, not whether or not it had cycles.
    Evidently we have been reading different references to glean our terminology; in the Lisp standard, any list with a cycle is circular.

  7. #7
    Join Date
    Feb 2008
    Posts
    966

    Re: How to find whether a linked list is a circular linked list

    Quote Originally Posted by pm_kirkham
    Evidently we have been reading different references to glean our terminology; in the Lisp standard, any list with a cycle is circular.
    The difference between a Circular Linked List, and a Linked List with cycles is that a list with cycles "may" be circular IFF the last element in the list points to the head of the list. The "modern" definition of a circular linked list is one where the last element in the list points to the first element. No exceptions.

    Maybe you should stop trying to reference everything to Lisp. It's dead man, give it up!!!

  8. #8
    Join Date
    May 2011
    Posts
    2

    Re: How to find whether a linked list is a circular linked list

    For an even more detailed answer you can check out this link:

    http://www.programmerinterview.com/i...le-or-it-ends/

  9. #9
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,350

    Re: How to find whether a linked list is a circular linked list

    Quote Originally Posted by pm_kirkham
    Evidently we have been reading different references to glean our terminology; in the Lisp standard, any list with a cycle is circular.
    If we refer to the NIST dictionary of algorithms and data structures, a circular list is "a linked list in which the nominal tail is linked to the head".
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  10. #10
    Join Date
    May 2009
    Posts
    2,413

    Re: How to find whether a linked list is a circular linked list

    Quote Originally Posted by Zachm View Post
    I'm not sure what is "normal linear search", but a typical method of finding if a linked list is circular is:
    Is this algoritm better than storing every visited node in a hashmap?

  11. #11
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,006

    Re: How to find whether a linked list is a circular linked list

    Quote Originally Posted by nuzzle View Post
    Is this algoritm better than storing every visited node in a hashmap?
    As noted in the link jporter posted, I think hashmap would require O(n) storage while the pointer solution requires O(1) storage. I'd imagine that practically speaking, iterating through the list twice ("at two speeds") is faster than running a hash query on every step (even with equivalent time complexity).
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  12. #12
    Join Date
    May 2011
    Posts
    22

    Re: How to find whether a linked list is a circular linked list

    Hi.

    Please do not take my solutions tooo seriousely. The OP asked for a not linear algorithm.

    Simulation of atomic forces are not linear, they are quadratic, ... whatever. So just build a graph out of the linked list. Each connection should yield in forces to the connected elements that they will try to get to the distance "1". Additionaly all elements have a very low pushing force to each other element (nonlinear force of course :-). A little bit of nonlinear friction also should be added.

    If you simulate this threedimensional over a few thousend cycles there may be different results.
    1. It will not converge to a stable solution. The distance of some list elements will keep growing. --> there are at least two not connected parts of the list wich travel through space. --> no cyclic list.

    2. it will converge to a stable solution. Then add a little power wich will attract the graph to the x-y-plane. After a few thousend additional iterations print the parallel projection of the graph to the x-y-plane and perform a Blob analysis of the resulting picture. There are four possible results:
    a. the graph has no hole. --> no circle, no linked list.
    b. the graph has more than one hole --> no circular list.
    c. the graph has exact one hole, and the area is about pi r^2 with r = number of nodes / 2*pi --> the graph is circular
    d. as c, but with smaller area --> the graph looks like a 6 or like a § or something else, but not like an o.

    Maybe this ist not the fastest algorithm, but it will result in the prettiest pictures :-)

    And you can do all of the things above nonlinear.


    GMarco

  13. #13
    Join Date
    Sep 2012
    Posts
    1

    Re: How to find whether a linked list is a circular linked list

    I know that I am digging up an old post, but would this also work?

    bool circleFound(Node* headNode)
    {
    bool circleFound = false;
    hash_map <Node*,int> hashedNodes;
    Node * currNode = headNode;

    while(currNode)
    {
    if (hashedNodes[currNode] > 0)
    {
    circleFound = true;
    break;
    }
    hashedNodes[currNode] = 1;
    currNode = currNode->next;
    }
    return circleFound;
    }

  14. #14
    Join Date
    May 2009
    Posts
    2,413

    Re: How to find whether a linked list is a circular linked list

    Quote Originally Posted by jblackwood3 View Post
    but would this also work?
    That's what I suggested and it will work. Sooner or later when you traverse a list you either reach the end or if it's circular or has a loop you come back to where you were before and that can be detected by storing all visited node pointers.

    I wrote hashmap but I meant hashset. You really don't need the counters. You only need to know whether a node pointer is already present or not and for that a hashset is fine.

    That said the other approach with two racing pointers at different speeds probably is better, although a little harder to get your head around. Here's a summary. The hashset solution is categorized as "correct but space inefficient",

    http://ostermiller.org/find_loop_sin...nked_list.html
    Last edited by nuzzle; September 26th, 2012 at 02:17 AM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center