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