for linked we always have only head On Thu, Dec 8, 2011 at 11:40 PM, sayan nayak <[email protected]> wrote:
> @Himanshu: If I follow ur algo..then I have to remove the loop..Otherwise > there will not be any head for the reversed linked-list. > If u wanna say..First remove the loop,make it a normal linked list,reverse > it.and then again loop it remembering the > previous link..then it's possible.But the Time overhead will be huge. > > Regards, > Sayan > > > On Thu, Dec 8, 2011 at 11:34 PM, himanshu kansal < > [email protected]> wrote: > >> @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. >> > > -- > 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.
