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