# Merge k Sorted Lists Problem Solution

Merge k Sorted Lists Problem: You are given an array of `k` linked-lists `lists`, each linked-list is sorted in ascending order.

Example :

```Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6```

## 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)
while minHeap:
node = heappop(minHeap)
else:
tail.next = node
tail = tail.next
if node.next:
heappush(minHeap, node.next)
``````

## 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){
lists[i] = lists[i].next;
}
}
while(!pq.isEmpty()){
ListNode curr = pq.remove();
else
prev.next = curr;
prev = curr;
if(curr.next != null)
}
}
``````

## 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;
}
``````

## 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* tail;
if (l1->val < l2->val) {
l1 = l1->next;
} else {
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;
}``````