![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674197367039-Merge%20Sort%20Explanation.jpg\")
<\/p>\n<\/p>\n
In this article, we are going to discuss merge sort and how to merge k sorted lists.<\/p>\n
Merge sort example:-<\/strong><\/p>\n Now, we have a brief understanding of the merge sort algorithm.<\/p>\n But before learning how to merge k sorted linked lists, we have to first know how to merge two sorted linked lists.<\/p>\n Merging two sorted linked list Algorithm:<\/strong> We are given k linked lists each of length n. Each given linked list is sorted in non-decreasing order, Our task is to merge them into a single sorted (non-decreasing order) linked list and print the sorted linked list as output.<\/p>\n Examples:<\/strong> Output:<\/strong><\/p>\n Input:<\/strong><\/p>\n Output:<\/strong><\/p>\n Min-heap is a min priority queue. It is a complete binary tree having a root value smaller than both children\u2019s values. <\/p>\n We will use a min-heap to get the current minimum value node of linked lists.<\/p>\n The main intuition behind this approach is to maintain the current smallest element from all given linked lists and add that element i.e Node to the final linked list. Let\u2019s understand the algorithm step-wise.<\/p>\n Before understanding the algorithm let\u2019s go briefly through the min-heap data structure. Min-heap data structure is a type of data structure that has the smallest element among all elements in the heap on the top.<\/p>\n Create a min-heap of type Node because it will store the nodes of the linked list. First of all, insert the first node of all the \u2018k\u2019 linked lists.<\/p>\n Continue these following steps until the min-heap is not empty:-<\/p>\n Finally, the sorted linked list is ready. Return the head node of the merged list.<\/p>\n Code:<\/strong><\/p>\n\t\t\t\t\t\t![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674197367161-Merge%20Sort%20Explanation1.png\")
<\/p>\nHow to Merge K Sorted Linked Lists<\/h3>\n
\nWhen the two recursive call will return the two sorted list, then we will merge those sorted list into a single list using these below steps.<\/p>\n\n
\nInput:<\/strong><\/p>\nk = 3, n = 3\nlist1 = 1->3->5->NULL\nlist2 = 2->4->8->NULL\nlist3 = 6->7->9->NULL<\/code><\/pre>\n1->2->3->4->5->6->7->8->9->NULL<\/code><\/pre>\nk = 2, n = 4\nlist1 = 2->3->10->12->NULL\nlist2 = 1->4->8->9->NULL<\/code><\/pre>\n1->2->3->4->8->9->10->12->NULL<\/code><\/pre>\nBrief about Min-Heap<\/h3>\n
2\n \/ \\\n 4 5\n \/ \\ \n 11 6 \n\n Min-Heap<\/code><\/pre>\nApproach:<\/h3>\n
Algorithm:<\/h3>\n
\n