Consider two linked lists l1 and l2. Create 2 hash maps,h1 and h2, one for each list with the format, <element, number of occurrence>.
Traverse one element in each list at a time. For each element in list l1, check whether it is present in h2. If yes, remove the element from h2 if the number of occurrence is 1 else reduce the number of occurrence of that element in hash map, h2. If the element is not present in hashmap, h2, insert the element in hashmap, h1 with number as occurrence as 1. Do the same with the other linklist, l2. Iterate over both the lists simultaneously. If a case is hit where we have some more elements in one list and we dont have in another list, abort since length of the list itself is not identical. If the length of both the lists are same, and we hit the end of the lists, check whether both the hash maps, h1 and h2 are empty. If empty, both lists are identical else they are not. The time complexity is less in this case, though the space complexity may be high especially when the lists are equal with no common elements between each lists. On 6/3/10, Anurag Sharma <[email protected]> wrote: > But perhaps the elements in lists may not be in order. > > Anurag Sharma > http://anuragsharma-sun.blogspot.com/ > > > On Thu, Jun 3, 2010 at 6:38 PM, Rohit Saraf > <[email protected]>wrote: > >> simple in place O(n lg n) solution. >> Choose a pivot in first array and partition it like in quicksort. >> Find the pivot in second array and partition. Now recurse on both >> halves. At any point if no of elements in array are not equal... >> Abort! >> >> >> -- >> -------------------------------------------------- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> -- >> 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]<algogeeks%[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. > > -- Sent from my mobile device Luv, S.Antony Vincent Pandian -- 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.
