Given two linked lists of integers. I was asked to return a linked list which contains the non-common elements. I know how to do it in O(n^2), any way to do it in O(n)?
A:
If they're unsorted, then I don't believe it is possible to get better than O(n^2). However, you can do better by sorting them... you can sort in reasonably fast time, and then get something like O(nlogn) (I'm not certain that's what it would be, but I think it can be that fast if you use the right algorithm).
rmeador
2010-06-18 22:43:46
It is possible to get better than O(n^2). See other solutions involving hash table.
Jamie Wong
2010-06-18 22:57:57
You can do an in-place mergesort on linked lists pretty fast - asymptotically in O(n log n). So yes, sorting then diffing will solve this in O(n log n). If you're not allowed to modify the original lists, then you can copy them, which is O(n), so it's still O(n log n).
Tom Anderson
2010-06-18 23:39:33
+2
A:
Use a hash table.
Iterate through the first linked list, entering the values you come across into a hash table.
Iterate through the second linked list, adding any element not found into the hash table into your list of non-common elements.
This solution should be O(n), assuming no collisions in the hash table.
Jamie Wong
2010-06-18 22:49:20