@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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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, רפי וינר <[email protected]> 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 [email protected]. >> > > To unsubscribe from this group, send email to >> > > [email protected]. >> > > 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
