Re: [algogeeks] Finding the middle of the linked list which has also cycle in the list
When the fast pointer points to head again, the slow pointer would point to the middle of the linked list. On Sat, Mar 27, 2010 at 11:51 PM, vikrant singh vikrantsing...@gmail.comwrote: Well gaurav, i think by this method you can only check for a cycle in the list. If u have any idea how can you implement this to solve originally posted problem? On Sat, Mar 27, 2010 at 9:03 AM, gaurav kishan gauravkis...@gmail.comwrote: Hi, Keep two pointers both initially pointing to Head. Move first pointer one by one and the second pointer by two nodes in each iteration. When second pointer next link points to head again,return first pointer. Please let me know if this can be further imporved upon or there is some fallacy in the approach. Regards, Gaurav. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- 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.comalgogeeks%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.
Re: [algogeeks] Finding the middle of the linked list which has also cycle in the list
vikrant you havent read properly the post by Gaurav when the second pointer will come back to the head first will be pointing the middle.(Think it)!! On Sun, Mar 28, 2010 at 10:21 AM, vikrant singh vikrantsing...@gmail.comwrote: Well gaurav, i think by this method you can only check for a cycle in the list. If u have any idea how can you implement this to solve originally posted problem? On Sat, Mar 27, 2010 at 9:03 AM, gaurav kishan gauravkis...@gmail.comwrote: Hi, Keep two pointers both initially pointing to Head. Move first pointer one by one and the second pointer by two nodes in each iteration. When second pointer next link points to head again,return first pointer. Please let me know if this can be further imporved upon or there is some fallacy in the approach. Regards, Gaurav. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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.
Re: [algogeeks] Finding the middle of the linked list which has also cycle in the list
@diamond sorry but how do we know the fast pointer is pointing to head again? u see, in case u dont have O(n) space to record visited nodes On Sun, Mar 28, 2010 at 10:28 AM, blackDiamond patidarc...@gmail.comwrote: vikrant you havent read properly the post by Gaurav when the second pointer will come back to the head first will be pointing the middle.(Think it)!! On Sun, Mar 28, 2010 at 10:21 AM, vikrant singh vikrantsing...@gmail.comwrote: Well gaurav, i think by this method you can only check for a cycle in the list. If u have any idea how can you implement this to solve originally posted problem? On Sat, Mar 27, 2010 at 9:03 AM, gaurav kishan gauravkis...@gmail.comwrote: Hi, Keep two pointers both initially pointing to Head. Move first pointer one by one and the second pointer by two nodes in each iteration. When second pointer next link points to head again,return first pointer. Please let me know if this can be further imporved upon or there is some fallacy in the approach. Regards, Gaurav. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- 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.
Re: [algogeeks] Finding the middle of the linked list which has also cycle in the list
in starting we keep track of head pointer.. we are having three pointers head,slower,faster, know we start traversing the list if(faster==head||faster-next==head) return slower else faster=faster-next-next slower=slower-next On Sun, Mar 28, 2010 at 12:15 PM, vikrant singh vikrantsing...@gmail.comwrote: @diamond sorry but how do we know the fast pointer is pointing to head again? u see, in case u dont have O(n) space to record visited nodes On Sun, Mar 28, 2010 at 10:28 AM, blackDiamond patidarc...@gmail.comwrote: vikrant you havent read properly the post by Gaurav when the second pointer will come back to the head first will be pointing the middle.(Think it)!! On Sun, Mar 28, 2010 at 10:21 AM, vikrant singh vikrantsing...@gmail.com wrote: Well gaurav, i think by this method you can only check for a cycle in the list. If u have any idea how can you implement this to solve originally posted problem? On Sat, Mar 27, 2010 at 9:03 AM, gaurav kishan gauravkis...@gmail.comwrote: Hi, Keep two pointers both initially pointing to Head. Move first pointer one by one and the second pointer by two nodes in each iteration. When second pointer next link points to head again,return first pointer. Please let me know if this can be further imporved upon or there is some fallacy in the approach. Regards, Gaurav. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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.
Re: [algogeeks] Finding the middle of the linked list which has also cycle in the list
if(faster==head||faster-next= =head) return slower else faster=faster-next-next slower=slower-next HERE we hv three poniter faster,headr,slower. as u hv mentioned that linked list has cycle list so better is that we hv to use for loop as :- if we take headr,link,temp; if(temp==headr) { link-temp=first; } else return temp; for(temp-first=null;tempheadr;temp-link++) { we can print the middle element; } or inplace of this we can use the pointer concept to assign the middle and faster element.. -- 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.
[algogeeks] Finding the middle of the linked list which has also cycle in the list
Hi, Keep two pointers both initially pointing to Head. Move first pointer one by one and the second pointer by two nodes in each iteration. When second pointer next link points to head again,return first pointer. Please let me know if this can be further imporved upon or there is some fallacy in the approach. Regards, Gaurav. -- 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.
Re: [algogeeks] Finding the middle of the linked list which has also cycle in the list
Well gaurav, i think by this method you can only check for a cycle in the list. If u have any idea how can you implement this to solve originally posted problem? On Sat, Mar 27, 2010 at 9:03 AM, gaurav kishan gauravkis...@gmail.comwrote: Hi, Keep two pointers both initially pointing to Head. Move first pointer one by one and the second pointer by two nodes in each iteration. When second pointer next link points to head again,return first pointer. Please let me know if this can be further imporved upon or there is some fallacy in the approach. Regards, Gaurav. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- 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.