```
class Solution {
public:
ListNode* merge2Lists(ListNode* head1 , ListNode*head2){
ListNode* d = new ListNode(0);
ListNode* e = d;
while(head1 && head2){
if(head1 -> val <= head2->val ){
e = e->next = head1;
head1= head1->next;
}
else if(head2 -> val < head1->val ){
e = e->next = head2;
head2= head2->next;
}
}
if(!head1) e->next =head2;
if(!head2) e->next = head1;
ListNode * ret =d->next;
delete d;
return ret;
}
ListNode* mergeKLists(vector<ListNode*>& a) {
int n = a.size();
if(n==0) return NULL;
while(n>1){
if(n%2 == 1) {a[n]=NULL;n++;} // to make n even
for(int i=0 ; i < (n)/2 ; i++ ){
a[i] = merge2Lists( a[i] , a[i+ (n/2)]);
}
n= n/2;
}
return a[0];
}
};
```