Re: [algogeeks] Finding the middle of a singly linked list which has a cycle in it
@Umer: Its a singly LL and it has cycle. Both N1 and N2 will keep traversing within the cycle. On Sun, Mar 28, 2010 at 9:56 PM, Umer Farooq the.um...@gmail.com wrote: I'll appreciate comments on the solution proposed by me. It works the following way: take two pointers, N1 and N2 pointing on the head of the list. Move N2 by two nodes, and N1 by a single node. When N2 reaches head again (or N2-Next is a head) then return N1 which will be pointing to the middle element of the list. Regards Umer Farooq On Sun, Mar 28, 2010 at 2:17 PM, Mukesh Kumar thakur mukeshraj8...@gmail.com wrote: hi! in my opinion we can find the middle element in the singly linked which hv the cycle as we know the list doesnt support the concept of cycle coz it has only one direction traversal but if we take the case when the list hvng the no of element equal as we hv : n element in the list we hv to find the middle one in genral;simply we divide it in . n/2; or if consider middle elment as a key temp-link=null; temp-first=middle -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, NMN -- 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 a singly linked list which has a cycle in it
that's why i have a terminating condition. It will keep on iterating until ((N2 != head)(N2-NextPtr != head)) is true. head pointer of the linked list will be passed as an argument to the function. On Mon, Mar 29, 2010 at 7:04 AM, Navin Naidu navinmna...@gmail.com wrote: @Umer: Its a singly LL and it has cycle. Both N1 and N2 will keep traversing within the cycle. On Sun, Mar 28, 2010 at 9:56 PM, Umer Farooq the.um...@gmail.com wrote: I'll appreciate comments on the solution proposed by me. It works the following way: take two pointers, N1 and N2 pointing on the head of the list. Move N2 by two nodes, and N1 by a single node. When N2 reaches head again (or N2-Next is a head) then return N1 which will be pointing to the middle element of the list. Regards Umer Farooq On Sun, Mar 28, 2010 at 2:17 PM, Mukesh Kumar thakur mukeshraj8...@gmail.com wrote: hi! in my opinion we can find the middle element in the singly linked which hv the cycle as we know the list doesnt support the concept of cycle coz it has only one direction traversal but if we take the case when the list hvng the no of element equal as we hv : n element in the list we hv to find the middle one in genral;simply we divide it in . n/2; or if consider middle elment as a key temp-link=null; temp-first=middle -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, NMN -- 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 a singly linked list which has a cycle in it
that will result into an infinite loop, On Mon, Mar 29, 2010 at 9:51 PM, Umer Farooq the.um...@gmail.com wrote: that's why i have a terminating condition. It will keep on iterating until ((N2 != head)(N2-NextPtr != head)) is true. head pointer of the linked list will be passed as an argument to the function. On Mon, Mar 29, 2010 at 7:04 AM, Navin Naidu navinmna...@gmail.comwrote: @Umer: Its a singly LL and it has cycle. Both N1 and N2 will keep traversing within the cycle. On Sun, Mar 28, 2010 at 9:56 PM, Umer Farooq the.um...@gmail.com wrote: I'll appreciate comments on the solution proposed by me. It works the following way: take two pointers, N1 and N2 pointing on the head of the list. Move N2 by two nodes, and N1 by a single node. When N2 reaches head again (or N2-Next is a head) then return N1 which will be pointing to the middle element of the list. Regards Umer Farooq On Sun, Mar 28, 2010 at 2:17 PM, Mukesh Kumar thakur mukeshraj8...@gmail.com wrote: hi! in my opinion we can find the middle element in the singly linked which hv the cycle as we know the list doesnt support the concept of cycle coz it has only one direction traversal but if we take the case when the list hvng the no of element equal as we hv : n element in the list we hv to find the middle one in genral;simply we divide it in . n/2; or if consider middle elment as a key temp-link=null; temp-first=middle -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, NMN -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, - Navin Mohan Naidu Great Minds Discuss Ideas Average Minds Discuss Events Small Minds Discuss People -- 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 a singly linked list which has a cycle in it
@Umer Farooq but cycle can be between the nodes(not like circular list) so we may not get head node. @all i think mukesh answer is right On Mon, Mar 29, 2010 at 9:21 AM, Umer Farooq the.um...@gmail.com wrote: that's why i have a terminating condition. It will keep on iterating until ((N2 != head)(N2-NextPtr != head)) is true. head pointer of the linked list will be passed as an argument to the function. On Mon, Mar 29, 2010 at 7:04 AM, Navin Naidu navinmna...@gmail.comwrote: @Umer: Its a singly LL and it has cycle. Both N1 and N2 will keep traversing within the cycle. On Sun, Mar 28, 2010 at 9:56 PM, Umer Farooq the.um...@gmail.com wrote: I'll appreciate comments on the solution proposed by me. It works the following way: take two pointers, N1 and N2 pointing on the head of the list. Move N2 by two nodes, and N1 by a single node. When N2 reaches head again (or N2-Next is a head) then return N1 which will be pointing to the middle element of the list. Regards Umer Farooq On Sun, Mar 28, 2010 at 2:17 PM, Mukesh Kumar thakur mukeshraj8...@gmail.com wrote: hi! in my opinion we can find the middle element in the singly linked which hv the cycle as we know the list doesnt support the concept of cycle coz it has only one direction traversal but if we take the case when the list hvng the no of element equal as we hv : n element in the list we hv to find the middle one in genral;simply we divide it in . n/2; or if consider middle elment as a key temp-link=null; temp-first=middle -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, NMN -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Prashant Kulkarni -- 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 a singly linked list which has a cycle in it
@black diamond i think u may b wrong. check out this 1-2-3-4-5-6-7-8-9-3-. . . . . . On Sat, Mar 27, 2010 at 11:04 AM, blackDiamond patidarc...@gmail.comwrote: take Two pointers increase one by 1 and other by two node if they match somewhere Firstone will become the middle.. On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.comwrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- 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.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 a singly linked list which has a cycle in it
@mukunda , looks like a v nice solution , but can u xplain the step 2 :line2 a bit more clearly? what do u mean by highest length pointer ? Please give an example to your solution. On Sun, Mar 28, 2010 at 9:23 AM, mukunda n s mukundn...@gmail.com wrote: Simplification of the problem would be find the node where the cycle starts then we can easily proceed as we do in singly linked list. 1-2-3-4-5-6-7-8-5 in this case it is 5 let pt1 points to 1(start node) step 1: Find one of nodes inside the cycle.. Proceed in the same way as we go to find whether cycle is there in the linked list or not.. Take 2 pointers increase one pointer ( pt2) by 1 and another pointer(pt3) by 2 when they meet we get a pointer inside the cycle(pt4) of the linked list.. step 2: Find the length(l1) of the list from pt1 to pt4 and then length(l2) of the cycle(pt4 to pt4) . . Now increase the highest length pointer by |l2-l1|..(i.e. if l1 is greater increase it by l1-l2.. l2 is greater increase it by l2-l1..) Now increase both the pointers in the same manner i.e. pt1 and pt4 when they meet we get the point where the cycle starts. step3: Now we know the start pointer and the end pointer...proceed in same manner as the finding the length in the non cyclic linked list.. Efficiency: O(n) On Sat, Mar 27, 2010 at 12:46 PM, saurabh gupta sgup...@gmail.com wrote: Perhaps, if n is the length (from the beginning to the point where the loop ends after a traversal of the loop) then n/2 is the middle, i.e. length of list / 2 in which case middle is easy to find. Is that the definition, Sanjana ? On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.comwrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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.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 a singly linked list which has a cycle in it
sorry, i forgot to see *singly* linked list. what about doing a topological sort and returning the middle element. -Rohit On Sun, Mar 28, 2010 at 11:54 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: @sanjana: but what in case of 1-2-3-1-4-5-6 -Rohit On Sat, Mar 27, 2010 at 11:19 PM, Sanjana - sanjana.2...@gmail.comwrote: For ex if there is 1-2-3-4-5-6-7-8-5 then no. of unique nodes is 8 then the loop keeps on repeating. So the middle is 4 or 5 On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.comwrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- 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.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.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 a singly linked list which has a cycle in it
this is impossible case.. how can node1 point to node2 as well as node4?... On Sun, Mar 28, 2010 at 11:54 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: @sanjana: but what in case of 1-2-3-1-4-5-6 -Rohit On Sat, Mar 27, 2010 at 11:19 PM, Sanjana - sanjana.2...@gmail.comwrote: For ex if there is 1-2-3-4-5-6-7-8-5 then no. of unique nodes is 8 then the loop keeps on repeating. So the middle is 4 or 5 On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.comwrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- 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.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.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.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 a singly linked list which has a cycle in it
@Rohit we have a cycle here using hare/tortoise find a node in the cycle find the length of the cycle. find the 'end' of the list, call it E Now equivalent to a singly linked list with the modified termination condition (you need to skip E when you hit it for the first time though) OR find the length of the 'prefix' which touches the cycle, you have the total length, answer = n/2. On Sun, Mar 28, 2010 at 12:43 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: sorry, i forgot to see *singly* linked list. what about doing a topological sort and returning the middle element. -Rohit On Sun, Mar 28, 2010 at 11:54 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @sanjana: but what in case of 1-2-3-1-4-5-6 -Rohit On Sat, Mar 27, 2010 at 11:19 PM, Sanjana - sanjana.2...@gmail.comwrote: For ex if there is 1-2-3-4-5-6-7-8-5 then no. of unique nodes is 8 then the loop keeps on repeating. So the middle is 4 or 5 On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.comwrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- 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.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.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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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 a singly linked list which has a cycle in it
@Rohit we have a cycle here On Sun, Mar 28, 2010 at 2:42 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: that is topologcall sort On 3/28/10, saurabh gupta sgup...@gmail.com wrote: @Rohit we have a cycle here using hare/tortoise find a node in the cycle find the length of the cycle. find the 'end' of the list, call it E Now equivalent to a singly linked list with the modified termination condition (you need to skip E when you hit it for the first time though) OR find the length of the 'prefix' which touches the cycle, you have the total length, answer = n/2. On Sun, Mar 28, 2010 at 12:43 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: sorry, i forgot to see singly linked list. what about doing a topological sort and returning the middle element. -Rohit On Sun, Mar 28, 2010 at 11:54 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @sanjana: but what in case of 1-2-3-1-4-5-6 -Rohit On Sat, Mar 27, 2010 at 11:19 PM, Sanjana - sanjana.2...@gmail.com wrote: For ex if there is 1-2-3-4-5-6-7-8-5 then no. of unique nodes is 8 then the loop keeps on repeating. So the middle is 4 or 5 On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.com wrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- 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.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.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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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. -- -Rohit -- 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. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears.
Re: [algogeeks] Finding the middle of a singly linked list which has a cycle in it
sry... i got confused -Rohit On Sun, Mar 28, 2010 at 3:14 PM, saurabh gupta sgup...@gmail.com wrote: @Rohit we have a cycle here On Sun, Mar 28, 2010 at 2:42 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: that is topologcall sort On 3/28/10, saurabh gupta sgup...@gmail.com wrote: @Rohit we have a cycle here using hare/tortoise find a node in the cycle find the length of the cycle. find the 'end' of the list, call it E Now equivalent to a singly linked list with the modified termination condition (you need to skip E when you hit it for the first time though) OR find the length of the 'prefix' which touches the cycle, you have the total length, answer = n/2. On Sun, Mar 28, 2010 at 12:43 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: sorry, i forgot to see singly linked list. what about doing a topological sort and returning the middle element. -Rohit On Sun, Mar 28, 2010 at 11:54 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @sanjana: but what in case of 1-2-3-1-4-5-6 -Rohit On Sat, Mar 27, 2010 at 11:19 PM, Sanjana - sanjana.2...@gmail.com wrote: For ex if there is 1-2-3-4-5-6-7-8-5 then no. of unique nodes is 8 then the loop keeps on repeating. So the middle is 4 or 5 On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.com wrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- 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 algogeeks@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.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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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. -- -Rohit -- 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. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is
Re: [algogeeks] Finding the middle of a singly linked list which has a cycle in it
anyways.. the solution becomes still more trivial... as there can be only one cycle remove it easily and that helps to find the centre. -Rohit On Sun, Mar 28, 2010 at 4:12 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: sry... i got confused -Rohit On Sun, Mar 28, 2010 at 3:14 PM, saurabh gupta sgup...@gmail.com wrote: @Rohit we have a cycle here On Sun, Mar 28, 2010 at 2:42 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: that is topologcall sort On 3/28/10, saurabh gupta sgup...@gmail.com wrote: @Rohit we have a cycle here using hare/tortoise find a node in the cycle find the length of the cycle. find the 'end' of the list, call it E Now equivalent to a singly linked list with the modified termination condition (you need to skip E when you hit it for the first time though) OR find the length of the 'prefix' which touches the cycle, you have the total length, answer = n/2. On Sun, Mar 28, 2010 at 12:43 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: sorry, i forgot to see singly linked list. what about doing a topological sort and returning the middle element. -Rohit On Sun, Mar 28, 2010 at 11:54 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @sanjana: but what in case of 1-2-3-1-4-5-6 -Rohit On Sat, Mar 27, 2010 at 11:19 PM, Sanjana - sanjana.2...@gmail.com wrote: For ex if there is 1-2-3-4-5-6-7-8-5 then no. of unique nodes is 8 then the loop keeps on repeating. So the middle is 4 or 5 On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.com wrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- 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.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.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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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. -- -Rohit -- 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
Re: [algogeeks] Finding the middle of a singly linked list which has a cycle in it
Hi, This one is rather easy.Same approach can be taken here what applies to non circular linked list. 1. Take a single pointer and a counter. Increment the counter till the next of pointer points to head of circular linked list. Reset the temp pointer to head and increment it to counter/2 + 1.If counter is even then there will be two elements for middle counter/2, counter/2 +1. 2.Take two temp pointers. Increment first by one and second by two positions. print the value of first when second reached the head. You have to put some checks for corner conditions. -- 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 a singly linked list which has a cycle in it
keep a ptr ( pt1) at the beginning of the list. do increase another pointer ( pt2) by 1 and another pointer(pt3) by 2 while ( pt3 does not point to the same location as pt1) On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.com wrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- 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.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 a singly linked list which has a cycle in it
Perhaps, if n is the length (from the beginning to the point where the loop ends after a traversal of the loop) then n/2 is the middle, i.e. length of list / 2 in which case middle is easy to find. Is that the definition, Sanjana ? On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.com wrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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 a singly linked list which has a cycle in it
For ex if there is 1-2-3-4-5-6-7-8-5 then no. of unique nodes is 8 then the loop keeps on repeating. So the middle is 4 or 5 On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.com wrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- 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.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.
