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]. > > > > > > 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. > > > > > > > > > > > > > > > > > > > > > -- > > > > > > > > > > > > > > > > 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. > > > > > > > > > > > > > > > > > > -- > > 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. > > > > > > -- > 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]. > 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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
