anyways.. the solution becomes still more trivial... as there can be only one cycle.... remove it easily and that helps to find the centre.
-Rohit On Sun, Mar 28, 2010 at 4:12 PM, Rohit Saraf <rohit.kumar.sa...@gmail.com>wrote: > sry... i got confused > -Rohit > > > > > On Sun, Mar 28, 2010 at 3:14 PM, saurabh gupta <sgup...@gmail.com> wrote: > >> @Rohit we have a cycle here >> >> On Sun, Mar 28, 2010 at 2:42 PM, Rohit Saraf <rohit.kumar.sa...@gmail.com >> > wrote: >> >>> that is topologcall sort >>> On 3/28/10, saurabh gupta <sgup...@gmail.com> wrote: >>> > @Rohit we have a cycle here >>> > >>> > using hare/tortoise find a node in the cycle >>> > find the length of the cycle. >>> > find the 'end' of the list, call it E >>> > Now equivalent to a singly linked list with the modified termination >>> > condition (you need to skip E when you hit it for the first time >>> though) >>> > OR >>> > find the length of the 'prefix' which touches the cycle, you have the >>> total >>> > length, answer = n/2. >>> > >>> > >>> > On Sun, Mar 28, 2010 at 12:43 PM, Rohit Saraf < >>> rohit.kumar.sa...@gmail.com> >>> > wrote: >>> > >>> > > >>> > > sorry, i forgot to see singly linked list. >>> > > >>> > > what about doing a topological sort and returning the middle element. >>> > > >>> > > >>> > > -Rohit >>> > > >>> > > >>> > > >>> > > >>> > > >>> > > >>> > > >>> > > >>> > > On Sun, Mar 28, 2010 at 11:54 AM, Rohit Saraf >>> > <rohit.kumar.sa...@gmail.com> wrote: >>> > > >>> > > > @sanjana: but what in case of 1->2->3->1->4->5->6 >>> > > > >>> > > > >>> > > > -Rohit >>> > > > >>> > > > >>> > > > >>> > > > >>> > > > >>> > > > >>> > > > >>> > > > On Sat, Mar 27, 2010 at 11:19 PM, Sanjana - < >>> sanjana.2...@gmail.com> >>> > wrote: >>> > > > >>> > > > > For ex if there is 1->2->3->4->5->6->7->8->5 then no. of unique >>> nodes >>> > is 8 then the loop keeps on repeating. So the middle is 4 or 5 >>> > > > > >>> > > > > >>> > > > > >>> > > > > On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf >>> > <rohit.kumar.sa...@gmail.com> wrote: >>> > > > > >>> > > > > > >>> > > > > > >>> > > > > > >>> > > > > > >>> > > > > > how do u define middle when there is a cycle in the list ? >>> > > > > > -Rohit >>> > > > > > >>> > > > > > >>> > > > > > >>> > > > > > >>> > > > > > On Sat, Mar 27, 2010 at 12:11 AM, Sanjana < >>> sanjana.2...@gmail.com> >>> > wrote: >>> > > > > > >>> > > > > > >>> > > > > > >>> > > > > > >>> > > > > > > Hello, >>> > > > > > > Can someone help me out with this. How to find the middle of >>> a >>> > singly >>> > > > > > > linked list which also has a cycle in it. >>> > > > > > > >>> > > > > > > -- >>> > > > > > > You received this message because you are subscribed to the >>> Google >>> > Groups "Algorithm Geeks" group. >>> > > > > > > To post to this group, send email to >>> algoge...@googlegroups.com. >>> > > > > > > To unsubscribe from this group, send email to >>> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> > > > > > > For more options, visit this group at >>> > http://groups.google.com/group/algogeeks?hl=en. >>> > > > > > > >>> > > > > > > >>> > > > > > >>> > > > > > >>> > > > > > >>> > > > > > >>> > > > > > >>> > > > > > >>> > > > > > -- >>> > > > > > >>> > > > > > You received this message because you are subscribed to the >>> Google >>> > Groups "Algorithm Geeks" group. >>> > > > > > To post to this group, send email to >>> algoge...@googlegroups.com. >>> > > > > > To unsubscribe from this group, send email to >>> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> > > > > > For more options, visit this group at >>> > http://groups.google.com/group/algogeeks?hl=en. >>> > > > > > >>> > > > > >>> > > > > >>> > > > > >>> > > > > -- >>> > > > > >>> > > > > >>> > > > > >>> > > > > You received this message because you are subscribed to the >>> Google >>> > Groups "Algorithm Geeks" group. >>> > > > > To post to this group, send email to algoge...@googlegroups.com. >>> > > > > To unsubscribe from this group, send email to >>> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> > > > > For more options, visit this group at >>> > http://groups.google.com/group/algogeeks?hl=en. >>> > > > > >>> > > > >>> > > > >>> > > >>> > > >>> > > >>> > > -- >>> > > You received this message because you are subscribed to the Google >>> Groups >>> > "Algorithm Geeks" group. >>> > > To post to this group, send email to algoge...@googlegroups.com. >>> > > To unsubscribe from this group, send email to >>> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> > > For more options, visit this group at >>> > http://groups.google.com/group/algogeeks?hl=en. >>> > > >>> > >>> > >>> > >>> > -- >>> > Man goes to doctor. Says he's depressed. Says life seems harsh and >>> cruel. >>> > Says he feels all alone in a threatening world where what lies ahead is >>> > vague and uncertain. Doctor says "Treatment is simple. Great clown >>> > Pagliacci is in town tonight. Go and see him. That should pick you >>> up." Man >>> > bursts into tears. Says "But, doctor...I am Pagliacci." >>> > >>> > >>> > -- >>> > You received this message because you are subscribed to the Google >>> Groups >>> > "Algorithm Geeks" group. >>> > To post to this group, send email to algoge...@googlegroups.com. >>> > To unsubscribe from this group, send email to >>> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> > For more options, visit this group at >>> > http://groups.google.com/group/algogeeks?hl=en. >>> > >>> >>> >>> -- >>> -Rohit >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> >> >> -- >> Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. >> Says he feels all alone in a threatening world where what lies ahead is >> vague and uncertain. Doctor says "Treatment is simple. Great clown >> Pagliacci is in town tonight. Go and see him. That should pick you up." >> Man >> bursts into tears. Says "But, doctor...I am Pagliacci." >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
