Node * N1, N2 = head
do {
..... N1 = N1->NextPtr;
......N2 = N2->NextPtr->NextPtr;
}while ((N2 != head)&&(N2->NextPtr != head))
return N1;
I think the above algorithm will work fine. N1 will be the middle element at
the end.
On Sun, Mar 28, 2010 at 4:53 AM, mukunda n s <mukundn...@gmail.com> wrote:
> 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 <sgup...@gmail.com> 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 <
>> 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.
>>>
>>
>>
>>
>> --
>> 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<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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
