You can construct some kind of Search Tree like BST from the first list and search for every element in the second list in that search Tree. O(NlogN) time
Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Wed, Jun 2, 2010 at 6:18 AM, sharad kumar <aryansmit3...@gmail.com>wrote: > @Raj:sorting can be done in O(nlogn)..sort both and compare both.or use a > hash map to store all elements of one LL and then compare it with > other....or combine both the LL perform merge sort and start deleting > adjacent elements.if adjacent elements in equal count then LL are equal and > at end of process we get an empty list..... > > > On Tue, Jun 1, 2010 at 11:55 PM, Raj N <rajn...@gmail.com> wrote: > >> Hi all, >> Can someone suggest an efficient algorithm to check if 2 linked lists >> are identical. If 2 lists have to be sorted then there'll be a lot of >> space consumption for 2 separate linked lists. Can the whole process >> be done < O(n2) >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > yezhu malai vaasa venkataramana Govinda Govinda > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
