Merge k Sorted Lists
Given an array of linked-lists lists, each linked list is sorted in ascending order.
Merge all the linked-lists into one sort 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: []
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists)
{
map<int,int> mp;
int n=lists.size();
if(n==0)
return NULL;
if(n==1&&lists[0]==NULL)return NULL;
for(int i=0;i<n;++i)
{
if(lists[i])
{ListNode *h=lists[i];
while(h->next)
{
mp[h->val]++;
h=h->next;
}
if(h)
mp[h->val]++;
}
}
ListNode* head=NULL,*p;
if(mp.size()>0)
{
auto it=mp.begin();
head=new ListNode(it->first);
p=head;
int f=1;
for(auto it=mp.begin();it!=mp.end();++it)
{
if(f==1)
{
it->second-=1;
f=0;
}
while((it->second)--)
{
p->next=new ListNode(it->first);
p=p->next;
}
}
}
return head;
}
};
----------------------------------------------------------------------------------------------------------------------------
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
self.nodes = []
head = point = ListNode(0)
for l in lists:
while l:
self.nodes.append(l.val)
l = l.next
for x in sorted(self.nodes):
point.next = ListNode(x)
point = point.next
return head.next
--------------------------------------------------------------------------------------------------------------------------
