# Leet Code : Merge k Sorted Lists C++ , Java , Python solution

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

Example 1:

```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
```

Example 2:

```Input: lists = []
Output: []
```

Example 3:

```Input: lists = [[]]
Output: []```

## C++ Solution :

``````class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {

if(lists.empty()) return nullptr;
ListNode* dummy = new ListNode(0);
ListNode* cp = dummy;
int cur = INT_MAX, index = 0;
while(1) {
cur = INT_MAX;
for(int i=0;i<lists.size();++i) {
if(lists[i] != NULL && lists[i]->val<cur) {
cur = lists[i]->val;
cp->next = lists[i];
index = i;
}
}
if(cur == INT_MAX) break;
lists[index] = lists[index]->next;
cp = cp->next;
}

return dummy->next;

}
};``````

## Java Solution :

``````Approach : Using Priority Queue
Step 1 : Convert Array of ListNode into PriorityQueue
Step 2 : Create a LinkedList with values from PriorityQueue
class Solution {
public ListNode mergeKLists(ListNode[] lists)
{
PriorityQueue<Integer> pq = new PriorityQueue<>();

// converting into Priority Queue
for(ListNode a : lists)
{
while(a != null)
{
a = a.next;
}
}

// Converting back to Linked List
ListNode ans = new ListNode();
if(pq.size() == 0)
{
return null;
}
else
{
ans.val = pq.poll();
ListNode temp = ans;
while(pq.size() != 0)
{
temp.next = new ListNode(pq.poll());
temp = temp.next;
}
return ans;
}
}
}
``````

## Python Solution

`````` def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:

n = len(lists)
if n == 0:
return None

if n == 1:
return lists

init = [(lists[i].val, i) for i in range(n) if lists[i]]
if not init:
return None

heapq.heapify(init)
result = ListNode()
while init:
value, index = heapq.heappop(init)
#index is the index of listnode
lists[index] = lists[index].next
#may be we push something
if not lists[index]:
continue
newValue = lists[index].val
if newValue < value:
#add this value to result and continue