Iterating each list is at least O(n) (because you just visited each item). So your dictionary building is in itself O(nlogn). As a minor optimization, when you

Iterating each list is at least O(n) (because you just visited each item). So your dictionary building is in itself O(nlogn). As a minor optimization, when you walk the last list you can build the final list incrementally (check for things with two existing visits).