if u cant create new ptrs....then i think horse and tortoise strategy will fail..... then you can only modify the linked lists to detect the loop.....
one other strategy could be to reverse the linked list.....after reversing the linked list, if you arrive at the head itself then the list contains the loop.... i know reversing of list will require additional three ptrs....bt this is also one of the way.... On Thu, Dec 8, 2011 at 9:43 PM, hary rathor <[email protected]> wrote: > take two pointer > run first with one speed and another with two until they meet, > now take a first pointer and assign with head of list . > now move again both same speed (only one forward at a time ) > now as they meet at point that will be your starting pointer of loop. > > On 12/8/11, Deepak Nettem <[email protected]> wrote: > > If you allow storing an extra bit with every node (to mark whether a node > > has been visited), you can do it with just one pointer. But that's less > > space efficient (O(n)) than using two pointers of varying speeds. > > > > On Thu, Dec 8, 2011 at 9:04 AM, Ankur Garg <[email protected]> wrote: > > > >> U cant create any new ptrs .Just use this ptr :) > >> > >> > >> On Thu, Dec 8, 2011 at 6:30 PM, Prem Krishna Chettri > >> <[email protected]>wrote: > >> > >>> Ofcourse we can.. > >>> > >>> U knw the head address now U start visit the list what is the big > >>> deal?? Jst u gotto create two pointer say fast and slow with two diff > >>> speed > >>> of action.. > >>> > >>> On Thu, Dec 8, 2011 at 6:27 PM, Ankur Garg <[email protected]> > wrote: > >>> > >>>> Can we detect if a loop is present in Linked List if only head ptr is > >>>> given > >>>> > >>>> -- > >>>> 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. > > > > > > > -- > Harish Pranami > Master Of Computer Application , > Deptt of computer Science, > north campus , university of delhi, > New Delhi pin no - 110007 > > -- > 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. > > -- Regards Himanshu Kansal Msc Comp. sc. (University of Delhi) -- 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.
