@sayan: take a singley linked list (not circular) with a loop in it....try to reverse it.....you will get why i gave this algo...it can be reversed....and it always ends up landing at original head of list if it contains a loop.... give it a try...
On Thu, Dec 8, 2011 at 11:30 PM, sayan nayak <[email protected]> wrote: > @Himanshu: How can u reverse a linked list which has only the > beginning(head) but no tail... > > And even if I consider that by some means u have reversed it..then also > there is no guarantee that u reach the head.. > Because the LinkedList is not necessarily circular..a circular Linkedlist > and a linkedlist with loop are not same...Cicular is one specific case of > Loop. > > Pls correct me If I have misunderstood your explanation. > > Regards, > Sayan > > > > On Thu, Dec 8, 2011 at 10:27 PM, himanshu kansal < > [email protected]> wrote: > >> 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. >> > > -- > 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.
