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 1:
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
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)
{
pq.add(a.val);
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[0]
init = [(lists[i].val, i) for i in range(n) if lists[i]]
if not init:
return None
heapq.heapify(init)
result = ListNode()
head = result
while init:
value, index = heapq.heappop(init)
#index is the index of listnode
head.next = lists[index]
head = head.next
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
head.next = lists[index]
lists[index] = lists[index].next
head = head.next
continue
heapq.heappush(init, (newValue,index))
return result.next