Union of Two Linked Lists using Merge Sort in C++

By Anirudh C V

We traverse given two linked list and return a sorted list which contains all the elements from first and second linked list only once.

We Merge sort the linked lists and find its Union

Let first linked list be : 5 -> 8 -> 2 -> 9 -> 1

Let second linked list be : 10 -> 4 -> 3 -> 6 -> 7

Then the sorted union of the two linked list would be : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

Let time complexity for sorting first linked list be O(n*log(n)) and second linked list be O(m*log(m)) where n,m  are number of elements in first and second linked list.

Therefore the Time complexity of this method is O(m*Log(m) + n*Log(n)) which is efficient for large number of elements.