Re: [algogeeks] Detect a loop with just head ptr given
for linked we always have only head On Thu, Dec 8, 2011 at 11:40 PM, sayan nayak 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 < > himanshukansal...@gmail.com> wrote: > >> @sayan: take a singley linked list (not circular) with a loop in >> ittry to reverse it.you will get why i gave this algo...it can be >> reversedand 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 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 < >>> himanshukansal...@gmail.com> wrote: >>> if u cant create new ptrsthen 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 ptrsbt this is also one of the way On Thu, Dec 8, 2011 at 9:43 PM, hary rathor 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 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 > wrote: > > > >> U cant create any new ptrs .Just use this ptr :) > >> > >> > >> On Thu, Dec 8, 2011 at 6:30 PM, Prem Krishna Chettri > >> 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 > 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 algogeeks@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. > > >>> > >>> -- > >>> You received this message because you are subscribed to the Google > Groups > >>> "Algorithm Geeks" group. > >>> To post to this group, send email to algogeeks@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. > >>> > >> > >> -- > >> You received this message because you are subscribed to the Google > Groups > >> "Algorithm Geeks" group. > >> To post to this group, send email to algogeeks@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. > >> > > > > > > > > -- > > > > -- > > You received this message because you are subscribed to the Google > Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at >
Re: [algogeeks] Detect a loop with just head ptr given
I appreciate everyone effort here but guy's the question here is to Not Use any More pointer (Rather Space Utilization).. I Donno , if there is a any way to detect without any further space.. Else my First Solution works neatly... Br, On Thu, Dec 8, 2011 at 11:34 PM, himanshu kansal < himanshukansal...@gmail.com> wrote: > @sayan: take a singley linked list (not circular) with a loop in ittry > to reverse it.you will get why i gave this algo...it can be > reversedand 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 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 < >> himanshukansal...@gmail.com> wrote: >> >>> if u cant create new ptrsthen 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 ptrsbt this >>> is also one of the way >>> >>> >>> On Thu, Dec 8, 2011 at 9:43 PM, hary rathor 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 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 wrote: > >> U cant create any new ptrs .Just use this ptr :) >> >> >> On Thu, Dec 8, 2011 at 6:30 PM, Prem Krishna Chettri >> 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 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 algogeeks@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. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@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. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@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. >> > > > > -- > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@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. > > -- 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 >>
Re: [algogeeks] Detect a loop with just head ptr given
@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 < himanshukansal...@gmail.com> wrote: > @sayan: take a singley linked list (not circular) with a loop in ittry > to reverse it.you will get why i gave this algo...it can be > reversedand 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 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 < >> himanshukansal...@gmail.com> wrote: >> >>> if u cant create new ptrsthen 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 ptrsbt this >>> is also one of the way >>> >>> >>> On Thu, Dec 8, 2011 at 9:43 PM, hary rathor 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 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 wrote: > >> U cant create any new ptrs .Just use this ptr :) >> >> >> On Thu, Dec 8, 2011 at 6:30 PM, Prem Krishna Chettri >> 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 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 algogeeks@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. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@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. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@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. >> > > > > -- > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@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. > > -- Harish Pranami Master Of Computer Application , Deptt of computer Science, north campus , university of delhi, New Delhi pin no -
Re: [algogeeks] Detect a loop with just head ptr given
@sayan: take a singley linked list (not circular) with a loop in ittry to reverse it.you will get why i gave this algo...it can be reversedand 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 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 < > himanshukansal...@gmail.com> wrote: > >> if u cant create new ptrsthen 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 ptrsbt this is >> also one of the way >> >> >> On Thu, Dec 8, 2011 at 9:43 PM, hary rathor 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 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 >>> wrote: >>> > >>> >> U cant create any new ptrs .Just use this ptr :) >>> >> >>> >> >>> >> On Thu, Dec 8, 2011 at 6:30 PM, Prem Krishna Chettri >>> >> 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 >>> 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 algogeeks@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. >>> >>> >>> >>> >>> -- >>> >>> You received this message because you are subscribed to the Google >>> Groups >>> >>> "Algorithm Geeks" group. >>> >>> To post to this group, send email to algogeeks@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. >>> >>> >>> >> >>> >> -- >>> >> You received this message because you are subscribed to the Google >>> Groups >>> >> "Algorithm Geeks" group. >>> >> To post to this group, send email to algogeeks@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. >>> >> >>> > >>> > >>> > >>> > -- >>> > >>> > -- >>> > You received this message because you are subscribed to the Google >>> Groups >>> > "Algorithm Geeks" group. >>> > To post to this group, send email to algogeeks@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. >>> > >>> > >>> >>> >>> -- >>> 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 algogeeks@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. >>> >>> >> >> >> -- >> >>Regards >> Himanshu Kansal >>Msc Comp. sc. >> (University of Delhi) >> >> >> -- >> You received this message because you are subscribed to the Google
Re: [algogeeks] Detect a loop with just head ptr given
@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 < himanshukansal...@gmail.com> wrote: > if u cant create new ptrsthen 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 ptrsbt this is > also one of the way > > > On Thu, Dec 8, 2011 at 9:43 PM, hary rathor 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 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 >> wrote: >> > >> >> U cant create any new ptrs .Just use this ptr :) >> >> >> >> >> >> On Thu, Dec 8, 2011 at 6:30 PM, Prem Krishna Chettri >> >> 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 >> 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 algogeeks@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. >> >> >>> >> >>> -- >> >>> You received this message because you are subscribed to the Google >> Groups >> >>> "Algorithm Geeks" group. >> >>> To post to this group, send email to algogeeks@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. >> >>> >> >> >> >> -- >> >> You received this message because you are subscribed to the Google >> Groups >> >> "Algorithm Geeks" group. >> >> To post to this group, send email to algogeeks@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. >> >> >> > >> > >> > >> > -- >> > >> > -- >> > You received this message because you are subscribed to the Google >> Groups >> > "Algorithm Geeks" group. >> > To post to this group, send email to algogeeks@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. >> > >> > >> >> >> -- >> 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 algogeeks@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. >> >> > > > -- > >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 algogeeks@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. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubsc
Re: [algogeeks] Detect a loop with just head ptr given
if u cant create new ptrsthen 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 ptrsbt this is also one of the way On Thu, Dec 8, 2011 at 9:43 PM, hary rathor 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 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 wrote: > > > >> U cant create any new ptrs .Just use this ptr :) > >> > >> > >> On Thu, Dec 8, 2011 at 6:30 PM, Prem Krishna Chettri > >> 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 > 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 algogeeks@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. > > >>> > >>> -- > >>> You received this message because you are subscribed to the Google > Groups > >>> "Algorithm Geeks" group. > >>> To post to this group, send email to algogeeks@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. > >>> > >> > >> -- > >> You received this message because you are subscribed to the Google > Groups > >> "Algorithm Geeks" group. > >> To post to this group, send email to algogeeks@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. > >> > > > > > > > > -- > > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@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. > > > > > > > -- > 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 algogeeks@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. > > -- 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 algogeeks@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.
Re: [algogeeks] Detect a loop with just head ptr given
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 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 wrote: > >> U cant create any new ptrs .Just use this ptr :) >> >> >> On Thu, Dec 8, 2011 at 6:30 PM, Prem Krishna Chettri >> 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 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 algogeeks@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. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@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. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@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. >> > > > > -- > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@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. > > -- 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 algogeeks@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.
Re: [algogeeks] Detect a loop with just head ptr given
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 wrote: > U cant create any new ptrs .Just use this ptr :) > > > On Thu, Dec 8, 2011 at 6:30 PM, Prem Krishna Chettri > 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 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 algogeeks@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. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@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. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@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. > -- -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] Detect a loop with just head ptr given
slight correction :head->next->IsVisited is true or false On Thu, Dec 8, 2011 at 6:42 PM, sayan nayak wrote: > It's possible if u modify the definition of the node itself. > add one variable ..let's say:IsVisited for every node. initialized to > false.And while traversing the list > make it true. > Now traverse it and check whether head->next is true or false. > If true return . > > But in this process original Linked list will be destroyed. > This process will use only one pointer..i.e.head pointer. > > Regards, > Sayan > > > On Thu, Dec 8, 2011 at 6:34 PM, Ankur Garg wrote: > >> U cant create any new ptrs .Just use this ptr :) >> >> >> On Thu, Dec 8, 2011 at 6:30 PM, Prem Krishna Chettri >> 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 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 algogeeks@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. >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@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. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@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. >> > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] Detect a loop with just head ptr given
It's possible if u modify the definition of the node itself. add one variable ..let's say:IsVisited for every node. initialized to false.And while traversing the list make it true. Now traverse it and check whether head->next is true or false. If true return . But in this process original Linked list will be destroyed. This process will use only one pointer..i.e.head pointer. Regards, Sayan On Thu, Dec 8, 2011 at 6:34 PM, Ankur Garg wrote: > U cant create any new ptrs .Just use this ptr :) > > > On Thu, Dec 8, 2011 at 6:30 PM, Prem Krishna Chettri > 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 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 algogeeks@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. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@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. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@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. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] Detect a loop with just head ptr given
U cant create any new ptrs .Just use this ptr :) On Thu, Dec 8, 2011 at 6:30 PM, Prem Krishna Chettri 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 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 algogeeks@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. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@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. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] Detect a loop with just head ptr given
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 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 algogeeks@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. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
[algogeeks] Detect a loop with just head ptr given
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 algogeeks@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.
