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

[rsodimbakam]

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

[Zachm]

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:

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

[ProgramThis]

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.

[pm_kirkham]

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.

[ProgramThis]

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.

[pm_kirkham]

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.

[nuzzle]

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?

[BioPhysEngr]

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).

[jporter]

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

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

[laserlight]

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".

[GMarco]

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

[jblackwood3]

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;
}

[nuzzle]

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