Simplification of the problem would be find the node where the cycle starts then we can easily proceed as we do in singly linked list. 1->2->3->4->5->6->7->8->5 in this case it is 5 let pt1 points to 1(start node) step 1: Find one of nodes inside the cycle.. Proceed in the same way as we go to find whether cycle is there in the linked list or not.. Take 2 pointers increase one pointer ( pt2) by 1 and another pointer(pt3) by 2 when they meet we get a pointer inside the cycle(pt4) of the linked list.. step 2: Find the length(l1) of the list from pt1 to pt4 and then length(l2) of the cycle(pt4 to pt4) . . Now increase the highest length pointer by |l2-l1|..(i.e. if l1 is greater increase it by l1-l2.. l2 is greater increase it by l2-l1..) Now increase both the pointers in the same manner i.e. pt1 and pt4 when they meet we get the point where the cycle starts.
step3: Now we know the start pointer and the end pointer...proceed in same manner as the finding the length in the non cyclic linked list.. Efficiency: O(n) On Sat, Mar 27, 2010 at 12:46 PM, saurabh gupta <[email protected]> wrote: > Perhaps, if n is the length (from the beginning to the point where the > loop ends after a traversal of the loop) then n/2 is the middle, > i.e. length of list / 2 > in which case middle is easy to find. > > Is that the definition, Sanjana ? > > 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. >> > > > > -- > 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.
