[algogeeks] Re: Y shaped linklist
*...@manisha one traversal for each of the lists * After* two traversals, *both pointers will surely meet at intersection point.. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Y shaped linklist
*...@manisha one traversal for each of the lists * --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Y shaped linklist
Correct. It will not be exactly one traversal of each list. More precisely, in worst case each pointer will traverse one list completely and then another list from beginning to intersection point. On Oct 11, 12:49 pm, ankur aggarwal ankur.mast@gmail.com wrote: *...@manisha one traversal for each of the lists * --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Y shaped linklist
@manisha that is the ques.. there are many soln for 2 traversal like loop in the linklist. simple travesal n many more.. On Sun, Oct 11, 2009 at 1:20 PM, ankur aggarwal ankur.mast@gmail.comwrote: *...@manisha one traversal for each of the lists * After* two traversals, *both pointers will surely meet at intersection point.. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Y shaped linklist
@sandeep notice that solution given on the given link doesn't satisfy the conditions given in the above question. @sharad Both lists may have duplicate values. So in this case it will better to hash the address of node instead of values. One other way is to maintain a flag in each of the node. In the begining flag will be 0 for all the items in both list. While traversing the first list, set the flags to 1. While traversing the seconds list,look for the item for which flag has been set. But this will also take additional o(n) space. I was thinking in line of reversing the first list while traversing it (it will use recursion). However, I couldn't make it work. Any thoughts? On Oct 10, 3:02 am, sandeep jain jainsandee...@gmail.com wrote: Here is one solutionhttp://geeksforgeeks.org/?p=2405 On Fri, Oct 9, 2009 at 9:00 AM, sharad kumar aryansmit3...@gmail.comwrote: space comp O(n) time o(2n) both in terms of worst case On Fri, Oct 9, 2009 at 8:46 PM, ankur aggarwal ankur.mast@gmail.comwrote: @sharad wat about space ?? extra space ? --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Y shaped linklist
One other way will be using two pointers. step1) Take two pointers(p1 and p2 ), pointing to the beginning of list L1 and L2. step2) Now start moving both the pointers simultaneously and check whether they point to same node. If not, then move both pointers to next node. Step3) If any of pointer becomes NULL then set it to the beginning of another list. Lets say p1 becomes NULL, then set p1 to point to L2. Step4) Repeat the step2 After two traversals, both pointers will surely meet at intersection point. On Oct 10, 3:24 pm, Manisha pgo...@gmail.com wrote: @sandeep notice that solution given on the given link doesn't satisfy the conditions given in the above question. @sharad Both lists may have duplicate values. So in this case it will better to hash the address of node instead of values. One other way is to maintain a flag in each of the node. In the begining flag will be 0 for all the items in both list. While traversing the first list, set the flags to 1. While traversing the seconds list,look for the item for which flag has been set. But this will also take additional o(n) space. I was thinking in line of reversing the first list while traversing it (it will use recursion). However, I couldn't make it work. Any thoughts? On Oct 10, 3:02 am, sandeep jain jainsandee...@gmail.com wrote: Here is one solutionhttp://geeksforgeeks.org/?p=2405 On Fri, Oct 9, 2009 at 9:00 AM, sharad kumar aryansmit3...@gmail.comwrote: space comp O(n) time o(2n) both in terms of worst case On Fri, Oct 9, 2009 at 8:46 PM, ankur aggarwal ankur.mast@gmail.comwrote: @sharad wat about space ?? extra space ? --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Y shaped linklist
hash one list and wen u traverse other check if prest in hash On Fri, Oct 9, 2009 at 10:02 AM, ankur aggarwal ankur.mast@gmail.comwrote: How to find the intersection point in linked list with the following constraints 1) one traversal for each of the lists 2) should not find the LENGTH of the lists 3) can USE recursion It goes like this ... --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Y shaped linklist
@sharad wat about space ?? extra space ? --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Y shaped linklist
space comp O(n) time o(2n) both in terms of worst case On Fri, Oct 9, 2009 at 8:46 PM, ankur aggarwal ankur.mast@gmail.comwrote: @sharad wat about space ?? extra space ? --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Y shaped linklist
Here is one solution http://geeksforgeeks.org/?p=2405 On Fri, Oct 9, 2009 at 9:00 AM, sharad kumar aryansmit3...@gmail.comwrote: space comp O(n) time o(2n) both in terms of worst case On Fri, Oct 9, 2009 at 8:46 PM, ankur aggarwal ankur.mast@gmail.comwrote: @sharad wat about space ?? extra space ? --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
