Circular linked list puzzle
-
Hi, Nope not homework. It was an interview question of a friend. I think I missed out some details when I gave the puzzle. We need to determine if the linked list is properly circular or not. Consider this linked list of 3 nodes A->B->C and C points back to B instead of A. Now according to your algorithm both the pointers will converge on some node, but the linked list is not a proper circular linked list. I was thinking more on the lines of storing the address of each node in some table as I parse down the list. Then if i come across a node whose entry already exists in the table and I haven't passed the starting node twice then it means there is some problem in the list. However my solution doesn't satisfy the condition of 2 pointers etc. -Mel
melwyn wrote: We need to determine if the linked list is properly circular or not. That wasn't suggested by your original post - it implied that there was a circle of some sort in the linked list, not that the whole list was either circular or straight :-) If it's properly circular, you only need to move a single pointer, with a second one pointing at the start, and you just wait for it to come around again (or hit the termination node). However, this means you can't determine if your list is "improperly" circular, as the moving pointer will get stuck in a loop and never return to the start. You can merge the two methods and use three pointers (start, slow and fast), which allows you to identify "properly", "improperly" and "not" circular lists, which would seem to me to be more useful. (Thinking about it, I'm sure Knuth would have solved this. I'll have to look it up properly tonight :-)) -- Ian Darling "The moral of the story is that with a contrived example, you can prove anything." - Joel Spolsky
-
Hi, Here's a puzzle. I have a linked list which may or may-not be circular. Using 2 pointers which have to be moving at any given point of time how do i determine if the linked list is circular? -Mel
Aha! (Another) classic Microsoft interview question! :) /ravi Let's put "civil" back in "civilization" Home | Articles | Freeware | Music ravib@ravib.com
-
melwyn wrote: We need to determine if the linked list is properly circular or not. That wasn't suggested by your original post - it implied that there was a circle of some sort in the linked list, not that the whole list was either circular or straight :-) If it's properly circular, you only need to move a single pointer, with a second one pointing at the start, and you just wait for it to come around again (or hit the termination node). However, this means you can't determine if your list is "improperly" circular, as the moving pointer will get stuck in a loop and never return to the start. You can merge the two methods and use three pointers (start, slow and fast), which allows you to identify "properly", "improperly" and "not" circular lists, which would seem to me to be more useful. (Thinking about it, I'm sure Knuth would have solved this. I'll have to look it up properly tonight :-)) -- Ian Darling "The moral of the story is that with a contrived example, you can prove anything." - Joel Spolsky
Your algorithm will work for non-proper linked lists as well. Start at the beginning of the list*. If there is a non-proper cycle in it, your pointers will indeed catch up with eachother sooner or later. Whip out your pen and paper and see for your self :)
le* first = list->head;
le* second = list->head ? list->head->next;while(second != first && second != NULL) {
second = second->next;
if(second != first && second != NULL) {
second = second->next;
first = first->next;
}
}if(second == NULL)
printf("No cycle\n");
else
printf("There is a cycle at %p (v = %d)\n", second, second->value);* Assume you don't start at the beginning of the list and there exists a cycle on the list prior to your start but no loop back to it. Then it is impossible to detect that cycle, since there is no way back to it. The problem stated a linked list, which I assume is a singly linked list, as doubly linked lists are usually named just that. A doubly linked list can be a bit trickier. Especially if for some i: i->prev->next != i. Not really sure about the implications of that as I don't feel a particular pressure to find out, but I'm sure it would make the problem a bit more fun. :) -- I can't resist a touch of evil.
-
Aha! (Another) classic Microsoft interview question! :) /ravi Let's put "civil" back in "civilization" Home | Articles | Freeware | Music ravib@ravib.com
Have you been an interviewee, or are you an interviewer? :) -- I can't resist a touch of evil.
-
(mmmm, smells like homework) Given you don't know whether it is or not, I would suggest you need to have a "slow" pointer and a "fast" pointer. For each time you move the slow pointer a single node along the linked list, you move the fast pointer on two nodes. If there is a circle, once both pointers are inside it the fast pointer will eventually "catch up" to the slow one, and they will both point at the same node (note that this isn't necessarily the "start" node of the circle, just a node within it). If the fast pointer reaches a terminating node, then there is (obviously) no circle. The performance characteristics aren't fantastic, but the algorithm should be sound. -- Ian Darling "The moral of the story is that with a contrived example, you can prove anything." - Joel Spolsky
Ian Darling wrote: (mmmm, smells like homework) It can't be homework! If it were homework, the poster would be smart enough to figure this out - since they were also clever enough to pose it as a "puzzle" instead of homework! :)
-
Your algorithm will work for non-proper linked lists as well. Start at the beginning of the list*. If there is a non-proper cycle in it, your pointers will indeed catch up with eachother sooner or later. Whip out your pen and paper and see for your self :)
le* first = list->head;
le* second = list->head ? list->head->next;while(second != first && second != NULL) {
second = second->next;
if(second != first && second != NULL) {
second = second->next;
first = first->next;
}
}if(second == NULL)
printf("No cycle\n");
else
printf("There is a cycle at %p (v = %d)\n", second, second->value);* Assume you don't start at the beginning of the list and there exists a cycle on the list prior to your start but no loop back to it. Then it is impossible to detect that cycle, since there is no way back to it. The problem stated a linked list, which I assume is a singly linked list, as doubly linked lists are usually named just that. A doubly linked list can be a bit trickier. Especially if for some i: i->prev->next != i. Not really sure about the implications of that as I don't feel a particular pressure to find out, but I'm sure it would make the problem a bit more fun. :) -- I can't resist a touch of evil.
Jörgen Sigvardsson wrote: Your algorithm will work for non-proper linked lists as well. I know that, that's what I originally set out to do (and I have the scribbles to prove it) :-D The debate was over truly circular linked lists :-) Jörgen Sigvardsson wrote: A doubly linked list can be a bit trickier. Especially if for some i: i->prev->next != i. Not really sure about the implications of that as I don't feel a particular pressure to find out, but I'm sure it would make the problem a bit more fun. :laugh: Yes. Couldn't find anything about this sort of problem in Knuths books at all - I'll have to write my own "solve stupid linked-list puzzles" book ;P -- Ian Darling "The moral of the story is that with a contrived example, you can prove anything." - Joel Spolsky
-
Jörgen Sigvardsson wrote: Your algorithm will work for non-proper linked lists as well. I know that, that's what I originally set out to do (and I have the scribbles to prove it) :-D The debate was over truly circular linked lists :-) Jörgen Sigvardsson wrote: A doubly linked list can be a bit trickier. Especially if for some i: i->prev->next != i. Not really sure about the implications of that as I don't feel a particular pressure to find out, but I'm sure it would make the problem a bit more fun. :laugh: Yes. Couldn't find anything about this sort of problem in Knuths books at all - I'll have to write my own "solve stupid linked-list puzzles" book ;P -- Ian Darling "The moral of the story is that with a contrived example, you can prove anything." - Joel Spolsky
Ian Darling wrote: Couldn't find anything about this sort of problem in Knuths books at all - I'll have to write my own "solve stupid linked-list puzzles" book Be sure to write your own imaginary CPU before you do! ;) -- I'm your turbo lover. Better run for cover![^]
-
Ian Darling wrote: (mmmm, smells like homework) It can't be homework! If it were homework, the poster would be smart enough to figure this out - since they were also clever enough to pose it as a "puzzle" instead of homework! :)
-
Aha! (Another) classic Microsoft interview question! :) /ravi Let's put "civil" back in "civilization" Home | Articles | Freeware | Music ravib@ravib.com
-
Have you been an interviewee, or are you an interviewer? :) -- I can't resist a touch of evil.
-
Your algorithm will work for non-proper linked lists as well. Start at the beginning of the list*. If there is a non-proper cycle in it, your pointers will indeed catch up with eachother sooner or later. Whip out your pen and paper and see for your self :)
le* first = list->head;
le* second = list->head ? list->head->next;while(second != first && second != NULL) {
second = second->next;
if(second != first && second != NULL) {
second = second->next;
first = first->next;
}
}if(second == NULL)
printf("No cycle\n");
else
printf("There is a cycle at %p (v = %d)\n", second, second->value);* Assume you don't start at the beginning of the list and there exists a cycle on the list prior to your start but no loop back to it. Then it is impossible to detect that cycle, since there is no way back to it. The problem stated a linked list, which I assume is a singly linked list, as doubly linked lists are usually named just that. A doubly linked list can be a bit trickier. Especially if for some i: i->prev->next != i. Not really sure about the implications of that as I don't feel a particular pressure to find out, but I'm sure it would make the problem a bit more fun. :) -- I can't resist a touch of evil.
Jörgen Sigvardsson wrote: The problem stated a linked list, which I assume is a singly linked list, as doubly linked lists are usually named just that. Actually the interviewer had mentioned that the linked list could be considered as doubly linked, if it could help solve the problem in any way.