Simple, refer this: http://www.geeksforgeeks.org/archives/2405
On Wed, May 2, 2012 at 1:12 AM, Abhishek Sharma <[email protected]>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 <[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. > -- 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.
