find intersection of 2 doubly linked lists

Question

I have an assignment where I need to find the intersections of 2 singly-linked (singly vs singly) lists. I also have to do it for 2 doubly linked (doubly vs doubly) lists:

• For singly linked list, I use mergeSort() to sort both lists and then compare item by item ==> O(m.log(m) + n.log(n))

• I am confused for doubly linked lists: the same could work, but I guess there might be a faster way.

Can someone please tell me if there is a more efficient way to find the intersection of the 2 doubly linked lists? I thought maybe we could merge them and check for duplicates, but I am not sure how that would work and how efficient it would be.

Edit: Note that 'intersection' here means a shared value, not a common node. Edit: the implementation should be done without the use of hashes

Answer 1

If one of the lists is very short or substantially shorter than the other, a simple nested linear scan with complexity O(n*m) may be faster than sorting the longer list. This is the best approach for very small n or m (1 or 0).

For the general case, you cannot suppose that the lists have no duplicates, so merging the lists would not help.

The is a potentially faster way to find the intersection of 2 lists, singly or doubly linked, or more generally the intersection of 2 sets, using a hash table:

• create an empty hash table that can hold duplicates;
• enumerate the first list, insert each element in the hash table: O(n);
• enumerate the second list, for each element, if it is found in the hash table, add it to the intersection and remove it from the hash table: O(m);
• discard the hash table.

The overall time complexity is O(n+m) using O(n) extra space. An extra advantage is the lists are not modified with this approach, which might be a requirement.