{"id":1806,"date":"2020-06-11T18:01:04","date_gmt":"2020-06-11T18:01:04","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1806"},"modified":"2022-11-28T07:15:45","modified_gmt":"2022-11-28T07:15:45","slug":"merge-k-sorted-linked-lists","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-linked-lists\/","title":{"rendered":"MERGE K SORTED LINKED LISTS"},"content":{"rendered":"

\"\"<\/p>\n

In this blog, we will discuss three different approaches to merge k sorted lists. Merging k sorted linked lists is a challenging topic and conquering it will make your data structures more efficient. Let\u2019s discuss how to merge k sorted lists.<\/p>\n

How to Merge K Sorted Linked List?<\/h2>\n
\n

Yor are given K sorted linked lists. You have to merge K sorted linked lists into one sorted list. The size of the linked list maybe different.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Example:<\/strong><\/p>\n

Input:\n[\nlist[1]:4\u2212>6\u2212>8\u2212>10\u2212>15\nlist[2]:1\u2212>5\u2212>9\nlist[3]:2\u2212>3\u2212>7\u2212>11\n]\n\nOutput: \n1\u2212>2\u2212>3\u2212>4\u2212>5\u2212>6\u2212>7\u2212>8\u2212>9\u2212>10\u2212>11\u2212>15<\/code><\/pre>\n
EXPLANATION:<\/h2>\n
Approach 1 To Merge K Sorted Lists(Brute force):<\/code><\/h3>\n
\n
All the given lists are sorted, which means that the head of each list would be the smallest element in its chain. So we could extract the minimum from the k head nodes and append it to the result list.<\/p>\n
Time complexity To Merge K Sorted Lists In Brute Force approach<\/code>: O(kN)<\/code> where k<\/code> is the number of linked lists. Almost every selection of nodes in the final link costs O(k)<\/code> (k-1 times comparison)<\/code>.<\/p>\n
Space complexity To Merge K Sorted Lists<\/code>: O(1)<\/code>. <\/p>\n<\/blockquote>\n
Approach 2 To Merge K Sorted Lists:<\/h3>\n
The idea is to insert all the node values from all the k<\/code> lists into an array. Sorting the array and creating a new linked list from the sorted array will give the required output.<\/p>\n
Pseudo code:<\/strong><\/p>\n
     ListNode mergeKLists(ListNode[] lists, int k)\n     {\n    \/\/ x array to store all the values from lists\n    int x[]\n    for(i = 0 to k) \n    {\n        ListNode temp = lists[i]\n        while(temp is not null)\n       {\n            \/\/ append the value of temp to x\n            x.add(temp.val)\n            temp = temp.next\n        }\n    }\n    \/\/ sort all the values of x\n    sort(x)\n    \/\/ Head node to return\n    ListNode head(-1)\n    ListNode temp = head\n    for(i = 0 to x.size()) {\n        ListNode newVal(x[i])\n        temp.next = newVal\n        temp = temp.next\n    }\n    return head.next\n    } <\/code><\/pre>\n
\n
TIME COMPLEXITY To Merge K Sorted Lists<\/code>: O(NlogN).
\nSPACE COMPLEXITY To Merge K Sorted Lists<\/code>: O(N),
\nwhere N<\/code> is the total number of nodes<\/p>\n<\/blockquote>\n
Approach 3 To Merge K Sorted Lists(Heaps):<\/code><\/h3>\n
    \n
  1. Create a priority queue.<\/li>\n
  2. Insert the first node from all the lists into the priority queue.<\/li>\n
  3. Loop until the priority queue is not empty Extract the minimum node from the queue and add it to our result list.<\/li>\n
  4. Add the next node (if present) from the extracted node list.<\/li>\n
  5. Return the resultant list.<\/li>\n<\/ol>\n
    SOLUTIONS To Merge K Sorted Lists:<\/h2>\n\t\t\t\t\t\t