@Umer your solution is the obvious one an so good. Bhupendra solution is much more efficient. @Abhishek solution is good bu requires more space. so to conclude Abhishek sol: space O(n+m) time O(n+m) Bhupendra sol: space O(1) time : O(n+m) Abhishek solution is good it the list are very long and combine in the beginning.
On May 1, 10:42 pm, Abhishek Sharma <jkabhishe...@gmail.com> wrote: > @Bhupendra: your approach is correct but in case the linked lists contain > millions of nodes then this might be an overhead. > > Another approach could be: > > - Start with the head of of both the lists. > - Store (Hash) the addresses to which the current nodes are pointing to, in > a hashtable. > - while storing (Hashing) also check if the address already exists (for > both of them). In case it exists in the hashtable, this address (or node) > is the required node else, increment the pointers to the next nodes. > > This algo will not require traversing the whole lists and will save time. > > Regards, > AB > > > > > > > > On Tue, May 1, 2012 at 9:36 PM, Umer Farooq <the.um...@gmail.com> wrote: > > You don't have to traverse the nodes of two lists simultaneously. > > > You have to check if the every node of list one matches with the address > > of any node of list two. The first matching address will be the output. > > > The worst case running time of this algo will be O(n^2) > > > On Tue, May 1, 2012 at 8:47 PM, rafi <rafiwie...@gmail.com> wrote: > > >> i dont understan if i look in the pic i attached then the length of > >> the first list is 5 and the length of the second list is 6. > >> what should i do now? > >> if i traverse the long list 5,6 nodes i dont get to the red node. > >> what am i missing? > > >> On 1 מאי, 18:04, Bhupendra Dubey <bhupendra....@gmail.com> wrote: > >> > start from head of both and as soon as one of the list is empty means > >> you > >> > hit null > >> > start counting the remaining number of nodes in the other list till that > >> > gets empty. > > >> > Now the number obtained above is the difference in length of the two > >> list > >> > prior to the first common node (the red node). Now again traverse the > >> > longer list corresponding to the above count and then start traversing > >> the > >> > other list .Stop when two nodes become equal. Home!:) > > >> > On Tue, May 1, 2012 at 7:55 PM, רפי וינר <rafiwie...@gmail.com> wrote: > >> > > you have two linked lists that some where combine in to one list. > >> > > pic attached to illustrate > >> > > [image: Inline image 1] > >> > > you need to find where the two list collide. (in the pic the red node) > > >> > > -- > >> > > 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. > > >> > -- > >> > bhupendra dubey > > >> > Untitled.png > >> > 14Kהצגהורדה > > >> -- > >> 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. > > > -- > > Umer > > > -- > > 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.
