-
October 10th, 2008, 02:39 AM
#1
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
-
October 10th, 2008, 03:43 AM
#2
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
-
October 10th, 2008, 12:30 PM
#3
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.
-
October 12th, 2008, 04:24 PM
#4
Re: How to find whether a linked list is a circular linked list
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.
-
October 13th, 2008, 12:44 PM
#5
Re: How to find whether a linked list is a circular linked list
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.
-
October 13th, 2008, 04:47 PM
#6
Re: How to find whether a linked list is a circular linked list
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.
-
October 14th, 2008, 08:10 AM
#7
Re: How to find whether a linked list is a circular linked list
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!!!
-
May 27th, 2011, 05:57 AM
#8
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/
-
May 28th, 2011, 12:50 AM
#9
Re: How to find whether a linked list is a circular linked list
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".
-
May 30th, 2011, 08:05 PM
#10
Re: How to find whether a linked list is a circular linked list
Originally Posted by Zachm
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?
-
June 10th, 2011, 11:24 PM
#11
Re: How to find whether a linked list is a circular linked list
Originally Posted by nuzzle
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.
-
June 13th, 2011, 10:04 AM
#12
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
-
September 25th, 2012, 06:26 PM
#13
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;
}
-
September 26th, 2012, 01:11 AM
#14
Re: How to find whether a linked list is a circular linked list
Originally Posted by jblackwood3
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 01: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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|