435,197 Members | 988 Online
Need help? Post your question and get tips & solutions from a community of 435,197 IT Pros & Developers. It's quick & easy.

 P: n/a How can I find a loop in a single linked list? I thought about keeping a flag or traversing list more than once...but it will require another data structure to store all these things... Also if the list is having many nodes then this won't ork.. So is there a full proof solution? Jun 21 '07 #1
11 Replies

 P: n/a On Jun 20, 10:11 pm, Shraddha

 P: n/a On Jun 21, 7:11 am, Shraddha

 P: n/a James Kanze wrote: > If you can modify the nodes in the list, you can add a flag, visited, which is initialized false. Loop, setting the flag true, until you find the end of the list, or a node with the flag true. If you encountered the end of the list, there's no cycle, loop again resetting the flag false (for the next time). If you encountered a node with the flag true, there's a cycle. To reset the flags, loop from the beginning, until you encounter a node with the flag reset. You don't need to go through the loop a second time if you also keep a flag telling you the state that you left visited nodes in the last time. Before starting the main loop you toggle that flag's value, then go through nodes checking whether the node's flag is equal to the outer flag; if so, you've got a loop; if not, set the node's flag equal to the outer flag. -- -- Pete Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The Standard C++ Library Extensions: a Tutorial and Reference." (www.petebecker.com/tr1book) Jun 21 '07 #4

 P: n/a On 21 Jun, 06:19, Naresh Rautela next) for(p1 = start; p1 != end; ++p1) { p2 = p1; ++p2 for(; p2 != end; ++p2) if(p1 == p2) ! there is a loop ! } not very efficient. regards DS Jun 21 '07 #5

 P: n/a On 21 Jun, 06:19, Naresh Rautela

 P: n/a On Jun 21, 1:33 pm, JT next; p2=p2->next; if (p2!=NULL) p2=p2->next; } return false; // No loop Jun 21 '07 #7

 P: n/a On Jun 21, 1:37 pm, JT next; p2=p2->next; if (p2!=NULL) p2=p2->next; } return false; // No loop Argg!!! I have egg on my face. :) I don't have my copy of the algorithm book with me, so I'm writing from memory. But there is a clear off-by-one error in my code. Let me try the 3rd time: (But surely, you get the idea by now. Whether my quick code has bug is irrelevant to whether this is a powerful classic technique) if (start==NULL) return false; // No loop, obviously node *p1=start; node *p2=start->next; while(p1!=NULL && p2!=NULL) { if (p1==p2) return true; // Infinite loop found! p1=p1->next; p2=p2->next; if (p2!=NULL) p2=p2->next; } return false; // No loop Jun 21 '07 #8

 P: n/a On 2007-06-21 07:19, Naresh Rautela wrote: On Jun 20, 10:11 pm, Shraddha How can I find a loop in a single linked list?I thought about keeping a flag or traversing list more than once...butit will require another data structure to store all these things...Also if the list is having many nodes then this won't ork.. So is there a full proof solution? Try the Hare and Tortoise approach. Basically have 2 ptrs both pointing to the start of the list. Increment one pointer by 1 and another by 2. After each increment comapre if they are equal. If there is a loop the pointers would meet. What is it that I am missing here, wouldn't the simplest approach be to store a pointer p1 to the "beginning" and then use another pointer p2 which walks the list, and for each new node p2 visits it tests to see if it's the one p1 points to. If there is a loop then you will discover that in N increments, and the same is true if there's no loop. If we look at the turtle and hare strategy we see that since the hare moves twice as fast as the turtle it will make two laps (if there's a loop) in the same time as the turtle makes one. So this means that we will find if there's a loop in 3N increments with this strategy and if there's no loop it will take 1.5N increments. -- Erik Wikström Jun 21 '07 #9

 P: n/a On Jun 21, 2:17 pm, Erik Wikström

 P: n/a On 2007-06-21 16:21, JT wrote: On Jun 21, 2:17 pm, Erik Wikström What is it that I am missing here, wouldn't the simplest approach be tostore a pointer p1 to the "beginning" and then use another pointer p2which walks the list, and for each new node p2 visits it tests to see ifit's the one p1 points to. If there is a loop then you will discoverthat in N increments, and the same is true if there's no loop. Your method works if the loop is a complete loop, but it doesn't work (and in fact goes into an infinite loop) if the loop begins half way. Say Node1.next == Node2 and Node2.next == Node3 and Node3.next == Node2 Then the tortoise/hare method will find it. I see. -- Erik Wikström Jun 21 '07 #11

 P: n/a On 21 Jun, 14:41, JT

### This discussion thread is closed

Replies have been disabled for this discussion.