Merge k Sorted Lists Problem: You are given an array of k
linked-lists lists
, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example :
Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6
Table of Contents
Merge k Sorted Lists Problem Solution
Problem Solution In Python
from heapq import *
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
setattr(ListNode, "__lt__", lambda self, other: self.val <= other.val)
minHeap = []
for root in lists:
if root:heappush(minHeap, root)
head, tail = None, None
while minHeap:
node = heappop(minHeap)
if not head:
head = tail = node
else:
tail.next = node
tail = tail.next
if node.next:
heappush(minHeap, node.next)
return head
Problem solution in Java.
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>(){
public int compare(ListNode n1, ListNode n2){
return n1.val-n2.val;
}
});
ListNode head = null, prev = null;
for(int i=0; i < lists.length; i++){
if(lists[i] != null){
pq.add(lists[i]);
lists[i] = lists[i].next;
}
}
while(!pq.isEmpty()){
ListNode curr = pq.remove();
if(head == null)
head = curr;
else
prev.next = curr;
prev = curr;
if(curr.next != null)
pq.add(curr.next);
}
return head;
}
Problem Solution In C++
class Solution {
public:
ListNode* merge(ListNode* a, ListNode* b){
ListNode* result = NULL;
if (a == NULL)
return b;
else if (b == NULL)
return a;
if (a->val <= b->val){
result = a;
result->next = merge(a->next, b);
} else {
result = b;
result->next = merge(a, b->next);
}
return result;
}
ListNode* mergeKLists(vector<ListNode*>& lists) { //merge pairs of lists in an iteration
if (lists.size() == 0)
return NULL;
for(int i = lists.size() ; i > 1 ; i = ceil((float) i/2)){
int j = 0;
while(j < i/2){
lists[j] = merge(lists[j], lists[i-j-1]);
j++;
}
}
return lists[0];
}
Problem Solution In C
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
while (listsSize > 1) {
bool odd = listsSize % 2;
listsSize -= odd;
for (int i = 0; i < listsSize; i+=2) {
struct ListNode* l1 = *(lists+i);
struct ListNode* l2 = *(lists+i+1);
if (l1 == 0) { *(lists + (i >> 1)) = l2; continue; }
if (l2 == 0) { *(lists + (i >> 1)) = l1; continue; }
struct ListNode* head;
struct ListNode* tail;
if (l1->val < l2->val) {
head = tail = l1;
l1 = l1->next;
} else {
head = tail = l2;
l2 = l2->next;
}
while (true) {
if (l1 == 0) { tail->next = l2; break; }
if (l2 == 0) { tail->next = l1; break; }
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
*(lists + (i >> 1)) = head;
}
if (odd) *(lists + (listsSize >> 1)) = *(lists + listsSize);
listsSize = (listsSize >> 1) + odd;
}
return *lists;
}