Union of Two Linked Lists using Merge Sort in C++
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.
Submitted by Anirudh C V (AnirudhCV)
Download packets of source code on Coders Packet