sry... i got confused -Rohit
On Sun, Mar 28, 2010 at 3:14 PM, saurabh gupta <[email protected]> wrote: > @Rohit we have a cycle here > > On Sun, Mar 28, 2010 at 2:42 PM, Rohit Saraf > <[email protected]>wrote: > >> that is topologcall sort >> On 3/28/10, saurabh gupta <[email protected]> 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 < >> [email protected]> >> > 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 >> > <[email protected]> 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 - <[email protected] >> > >> > 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 >> > <[email protected]> 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 < >> [email protected]> >> > 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 >> [email protected]. >> > > > > > > To unsubscribe from this group, send email to >> > [email protected]<algogeeks%[email protected]> >> . >> > > > > > > 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 [email protected] >> . >> > > > > > To unsubscribe from this group, send email to >> > [email protected]<algogeeks%[email protected]> >> . >> > > > > > 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 [email protected]. >> > > > > To unsubscribe from this group, send email to >> > [email protected]<algogeeks%[email protected]> >> . >> > > > > 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 [email protected]. >> > > To unsubscribe from this group, send email to >> > [email protected]<algogeeks%[email protected]> >> . >> > > 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 [email protected]. >> > To unsubscribe from this group, send email to >> > [email protected]<algogeeks%[email protected]> >> . >> > 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
