CareerCup

A linked list that is standalone will not share its final node with any other list. So, traverse all the lists, and store all the final nodes as keys in a map, associating final nodes with (linked list head, count) pairs. In the end, iterate through all the key-value pairs, and when count == 1, include the linked list head in the output.

If there's a grand total of D elements distributed throuhout K lists, the runtime here will be O(D+K), which is optimal.

If you didn't want to use a map, you could get O(D + KlogK) with a sort.

cant properly understand what question demands.. please elaborate if possible..

A standalone linked list has distinct start and end nodes.

Approach - Assume that all linked lists are unique to start with. Repeat for each linked list. Compare head with head of other linked lists. Navigate to the tail and compare with other tails. If head or tail is not unique, then not unique.

I agree to @rockstar's comment. The question is not clear. Pls elaborate.

In any case it's better to sort. Need an array to store heads (M in no.) of resulting lists. Sort this array in MlogM. Now, for every original linked list (N in no.), find it's head(in logM) in just sorted heads. If found, traverse it completely to check with the original list, if they are same, add respective head to the answer.
Total time complexity: O(MlogM)+O(NlogM)+O(N*avg_no_in_merged_lists).