Author |
Topic: cs: linked list loop (Read 8227 times) |
|
cnmne
Guest
|
This seems like a brute force method. Does anyone have a better solution? In other words, is there a solution that does not involve comparing every element to every other?
This does not assume that the loop refers to the first element, which would be the simple case. I toyed with an array of elements to test against but it did not seem any better. And of course recursion is not constant memory, not that it would really help.
If there is a maximum list length, one optimization would be to count the elements in the list up to that limit. Hitting the limit would imply a looped list. No limit was provided in the original problem though.
struct LinkedListElement {
LinkedListElement *next;
};
LinkedListElement *IsLinkedListLooped( LinkedListElement *inList ) {
LinkedListElement *last , *loop;
long index , count = 0;
for ( last = inList ; last ; last = last->next ) {
index = 0;
for ( loop = inList ; loop != last ; loop = loop->next ) {
index += 1;
}
if ( index != count ) {
break;
}
count += 1;
}
return last;
}
|
|
 IP Logged |
|
|
|
S. Owen
Full Member
Gender: 
Posts: 221
|
 |
Re: cs: linked list loop
« Reply #1 on: Jul 27th, 2002, 12:41pm » |
 Quote  Modify
|
Say that the loop starts at the kth node in the list, and has length m. That is, node m+k points back to node k. There are n = m+k nodes in all. These are just for notational convenience - we know none of these values at the outset.
Start a pointer A traversing the list from the beginning. Simultaneously, start a second pointer B traversing the list from the start, except have it move 2 elements at a time, not 1. I claim that the pointers will definitely meet up again in O(n) time if the list has a loop.
Consider time t >= k (after both pointers are in the loop). Their positions (the nodes they are current pointing to) are given by:
A: ( t-k (mod m) ) + k
B: ( 2t-k (mod m) ) + k
When do they meet? Well:
( 2t-k (mod m) ) + k = ( t-k (mod m) ) + k
2t-k (mod m) = t-k (mod m)
2t-k - (t-k) (mod m) = 0
t (mod m) = 0
So, when t = m, they must meet. This is O(n) time since m <= n. Knowing the length of the loop, m, one can then calculate k, where the loop starts.
|
|
IP Logged |
|
|
|
Alex Harris
Guest
|
Maybe I'm missing something obvious, but I don't see how knowing m gives us k. If it does then kindly ignore the stuff I have below 
Here is my code for determining the first element on the loop:
Let x = the head of the list
Let y = some point on the loop (e.g. the place we detected the loop)
findloophead(x,y){
pointers t, a=x, b=next(y), c=y
while (1) {
t=midpoint (a,c)
if find (b,t,c)
then c=t
else a=next(t)
t=midpoint (b,c)
if find (a,t,c)
then c=t
else b=next(t)
if (a==b) then return a
if (a==c) or (b==c) then return c
}}
midpoint (e,f): returns the pointer to the middle element (round toward front of list) --- we can implement this with a pointer+double speed pointer walk
find (e,f,g): returns true if we encounter f in a walk from e to g, otherwise false.
Constant memory, O(n) time.
The key to seeing that we meet the time constraint is to note that after each iteration of the while loop both of our testing zones (a,c) and (b,c) are at least cut in half. This means that in each successive iteration of the while loop our calls to midpoint() and find() cost about half as much. I am of course assuming pointers are constant memory but for whatever its worth I'm avoiding the assumption that we can store/manipulate numbers of O(n) in constant memory.
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: cs: linked list loop
« Reply #3 on: Jul 28th, 2002, 6:01pm » |
Quote Modify
|
Hmm, you're right. k isn't uniquely determined actually, now that I dig into it. You do know that the first element of the loop is somewhere in the m node up to and and including the node where the pointers meet, for what it's worth.
I'll see if I can come up with a quicker solution but yours looks good.
|
|
IP Logged |
|
|
|
nakaduct
Newbie
Posts: 2
|
|
Does the problem require m or k?
« Reply #4 on: Jul 29th, 2002, 12:04pm » |
Quote Modify
|
I don't see anything in the problem that demands finding m or k: the wording is "find a loop in a singly-linked list," which I interpreted as "return true if looped, else false".
In that case the problem is easier still: when n==2i, store pn. Compare each subsequent p with pn, until n==2i again.
In simpler terms: if you don't encounter the 8th element between 9 and 16, you know it's outside the loop and can move on to the 16th element. This requires at most 2n traversals (vs 3n for the double-hop solution above).
|
|
IP Logged |
|
|
|
-D-
Guest
|
nakaduct, what is i? Could you please elaborate your solution more, it sounds interesting but I don't quite understand what you're saying. thanks.
-D-
|
|
IP Logged |
|
|
|
Alex Harris
Guest
|
I'm not sure I fully understood what nakaduct is attempting to describe, ,but here are few points responding to it as far as I understood it.
The interpretation of the problem is certainly open to debate but I think since the limited interpretation of "detecting" a loop is so simple its more intersting to talk about finding the exact location of the loop.
For my answer I was not assuming we can store and play with O(n) numbers in constant space, because technically numbers of that size take theta(log(n)) space to store. I do assume we can store and act on pointers because otherwise nothing can be done. Assuming we can store O(n) numbers isn't crazy as they would generally be the same size as pointers, but I thought it was more interesting to not make that assumption. This, plus general simplicity, is why I did the midpoint with a double speed walk rather than getting a slightly better constant by keeping track of interval lengths.
Finally I think you're missing something in your solution description. When you don't see element 8 in a walk from 9 to 16, that means that EITHER 8 isn't in the loop OR the entire loop isn't contained in the run from 9-->16. You've omitted that second possiblity in your method.
|
|
IP Logged |
|
|
|
-D-
Guest
|
|
SLL's can do without them, can't do without O(n)..
« Reply #7 on: Jul 29th, 2002, 4:49pm » |
Quote Modify
 Remove
|
I had to take a pencil and paper to your solution Alex. It's a pretty slick way of imposing a binary search onto a SLL. But finding the midpoint imposes the O(n) limitation. I first set out to prove it wasn't O(n) then instead had to prove to myself it wasn't O(log(n))...
One alternate solution? not really feasible but theoretically would work. If we know a maximum potential 'n = m+k' we could hash all pointers until we found a pointer already hashed. Constant space to build a hash table, just a LOT of space. You would find the link in O(n) time also.
-D-
|
|
IP Logged |
|
|
|
Alex Harris
Guest
|
Thanks for the compliment -D-, but I have to nitpick with your hash table idea . The hash table is going to take theta(k) space and k is worst case theta(n). By putting a fixed bound like n < N you're taking the asymptotic aspect of the problem away, and any solution will be constant time and space since N is just a constant.
It doesn't seem plausible that we'd do better than O(n) time since in general we'll need that just to walk to the beginning of the loop even if we're told its position from the start.
|
|
IP Logged |
|
|
|
-D-
Guest
|
yeah, i realized a bit after posting that with the assumption I made you might as well traverse every element and if you take more than n steps you know there's a loop anyway.
-D-
|
|
IP Logged |
|
|
|
nakaduct
Newbie
Posts: 2
|
|
Re: cs: linked list loop
« Reply #10 on: Jul 31st, 2002, 4:20pm » |
Quote Modify
|
Quote:| (from an earlier poster:) What is i? |
|
Any integer. You store p2, then overwrite with p4, etc.
on Jul 29th, 2002, 1:52pm, Alex Harris wrote:| not assuming we can store and play with O(n) numbers in constant space, because technically numbers of that size take theta(log(n)) space to store. O(n) numbers ... would generally be the same size as pointers, |
|
Actually, equal size or smaller. I considered this before, but rejected it: if you can store a pointer that uniquely identifies 1 of n objects, then you can store n.
Those are my only storage requirements: the last pointer whose ordinal number was an exponent of 2, and the current value of n.
Quote:| When you don't see element 8 in a walk from 9 to 16, that means that EITHER 8 isn't in the loop OR the entire loop isn't contained in the run from 9-->16. |
|
The second case is covered in the walk from 17 to 32. I was sloppy in my language when I said you can conclude 8 is outside the loop; the 9-to-16 walk only tells you that n>8.
|
| « Last Edit: Jul 31st, 2002, 4:27pm by nakaduct » |
IP Logged |
|
|
|
-D-
Guest
|
|
Re: cs: linked list loop
« Reply #11 on: Jul 31st, 2002, 10:28pm » |
Quote Modify
Remove
|
nakaduct. I think I understand your solution now, that's pretty slick. What if we used a higher base? Would it find a loop quicker or would it just incur more loops?
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: cs: linked list loop
« Reply #12 on: Jul 31st, 2002, 11:36pm » |
Quote Modify
|
In a normal situation its true (as I said) that pointers into n items must be at least log n bits. However when dealing with computation questions where you have restricted resources its often interesting to see exactly what you can live without. We could imagine some special embedded hardware which gets a few built in pointer registers to some giant external data set and instead of getting full arithmetic on the pointer registers it just gets the ability to do compare's and next's.
The algorithm you present does solve the "detect" question in at worst about 2n nexts and 2n compares vs the worst case 3n nexts and 2n compares of the double speed pointer walk.
The question statement is perhaps ambiguous but its way too easy if all you have to do is detect that the loop exists or find an arbitrary element in the loop. Once would imagine that the "find the loop start" algorithm would be handy to call for turning lists with loops into non-looped lists. It's a small modification to change the algorithm I gave to one which gives you a pointer to the last loop element for example which you can set to
If we're going for constant optimization then a fair bit can be done to the find algorithm I gave but it does make it a bit less clear whats going on. For example, you can often piggyback the midpoint calls on the previous find call and wind up paying essentially 0 for them in many cases.
|
|
IP Logged |
|
|
|
Paul Hsieh
Guest
|
This is a classic problem in CS. For an interesting perspective look up the "Pollard Rho" factoring algorithm.
There are two major "fast" solutions, which I will label "race cars" and "anchor". For those that know the answers, they should know what I am talking about.
Like other linked list problems, its interesting to consider the case where the linked list is on disk. In this case like the other linked list question given here, its interesting that in general the "anchor" solution is 50% better than the "race car" solution just in pure access time.
I have given this question in interviews and I am surprised that among those who do not get the O(n) solutions, they cannot get any of the O(n2) solutions either! While I have gotten a number of correct O(n) solutions, I have never gotten a correct O(n2) solution from a candidate. Bizarre.
|
|
IP Logged |
|
|
|
Yossarian
Guest
|
Another improvement of the task :
Find out if there are loops in oriented graph
with single starting node (tree-like).
Given the starting node, you need to prove
or disprove that there are loops.
Graph is oriented, so two arcs pointing
to the same node do not make a loop.
a -> b -> c | This is not
a -> c | a loop
Loop is when there is something like
a -> b -> ... -> a
P.S. I had to solve this in T-SQL a week ago 
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: cs: linked list loop
« Reply #15 on: Aug 13th, 2002, 5:41am » |
Quote Modify
|
This is checking a (supposed) DAG for a loop, slightly specialized since you know you have a single "tree" and not a forest. Do a DFS and see if you have any back edges (edges which point back to the "active" path), if so thats a loop, if not there are no loops.
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: cs: linked list loop
« Reply #16 on: Aug 13th, 2002, 6:57am » |
Quote Modify
|
The only problem with the last two solutions is that you cannot modify the list at all, and can only use constant additional memory. So I dont' see a way to record what you have visited on the current search path, and detect a back edge that way.
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: cs: linked list loop
« Reply #17 on: Aug 13th, 2002, 12:26pm » |
Quote Modify
|
My last post wasn't a solution to the original problem it was a solution to the new problem stated by Yossarian. I hadn't interpreted him to be asking for a constant memory solution. If we need linear time and constant space for the detect cycles algorithm I'll go back to the drawing board 
|
|
IP Logged |
|
|
|
lovey
Newbie
Posts: 6
|
|
Re: cs: linked list loop
« Reply #18 on: Mar 13th, 2004, 6:00pm » |
Quote Modify
|
on Jul 28th, 2002, 6:01pm, srowen wrote:Hmm, you're right. k isn't uniquely determined actually, now that I dig into it. You do know that the first element of the loop is somewhere in the m node up to and and including the node where the pointers meet, for what it's worth.
I'll see if I can come up with a quicker solution but yours looks good. |
|
As proved earlier that both pointers meet at t=m , the head of the node is k nodes forward from this point. Start a new pointer from the head of the list say X. and have another one at meeting point say Y. increment both of them by one till they meet. They will meet exactly after k steps which is the head of the loop.
|
|
IP Logged |
|
|
|
GowriKumar
Junior Member
Gender:
Posts: 55
|
|
Re: cs: linked list loop
« Reply #19 on: Mar 6th, 2008, 4:52am » |
Quote Modify
|
on Aug 6th, 2002, 9:24pm, Paul Hsieh wrote:This is a classic problem in CS. For an interesting perspective look up the "Pollard Rho" factoring algorithm.
There are two major "fast" solutions, which I will label "race cars" and "anchor". For those that know the answers, they should know what I am talking about.
|
|
Could someone throw light on the two major solutions mentioned here?( "race cars" and "anchors" )
I'm just guessing,
Race cars, might be the two pointer method, where one is incremented by one and the other by two pointers.
But not sure about the anchor method.
Regards,
Gowri Kumar
|
|
IP Logged |
www.gowrikumar.com
|
|
|
coderyogi
Newbie
Posts: 29
|
|
Mathematical proof of lonked list loop
« Reply #20 on: Jun 19th, 2009, 8:14pm » |
Quote Modify
|
Is there a mathematical way to prove that a particular linked list does indeed contain a loop?
|
| « Last Edit: Jun 19th, 2009, 8:15pm by coderyogi » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: cs: linked list loop
« Reply #21 on: Jun 20th, 2009, 4:50am » |
Quote Modify
|
Depends what you call mathematical. A procedure can tell for sure.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Mathematical proof of lonked list loop
« Reply #22 on: Jun 20th, 2009, 5:19am » |
Quote Modify
|
on Jun 19th, 2009, 8:14pm, coderyogi wrote:| Is there a mathematical way to prove that a particular linked list does indeed contain a loop? |
|
What do you mean by a "mathematical way"? Isn't an algorithm good enough? And if not, what would be?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Mathematical proof of lonked list loop
« Reply #23 on: Jun 20th, 2009, 5:39am » |
Quote Modify
|
on Jun 20th, 2009, 5:19am, towr wrote:
What do you mean by a "mathematical way"? Isn't an algorithm good enough? And if not, what would be?
|
|
Can you tell me what is the question? The first post of this thread doesn't state the problem. And I don't want to read all the suggested solutions to guess the problem.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Mathematical proof of lonked list loop
« Reply #24 on: Jun 20th, 2009, 6:05am » |
Quote Modify
|
on Jun 20th, 2009, 5:39am, R wrote:| Can you tell me what is the question? |
|
I think the question was probably to find and/or remove a loop from a linked list. (i.e. the last element's next pointer points to one of the earlier elements)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print