# Solution by <644367822>

• #### Approach #1 Brute Force [Accepted]

Algorithm

This is a simple solution , we merge each two lists from 0 to k ( lists size ) .
We can refer to 21. Merge Two Sorted Lists

c++

``````class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* head = new ListNode(0) ;
while( l1 != NULL && l2 != NULL ) {
if( l1->val <= l2->val ) {
p->next = l1 ;
p = p->next ;
l1 = l1->next ;
}
else {
p->next = l2 ;
p = p->next ;
l2 = l2->next ;
}
}
if( l1 != NULL ) {
p->next = l1 ;
}
else if( l2 != NULL ) {
p->next = l2 ;
}
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if( lists.size() == 0 ) {
return NULL;
}
ListNode *ans = lists [0] ;
for( int i = 1 ;i < lists.size() ; i ++ ) {
ans = mergeTwoLists( lists[i] , ans ) ;
}
return ans ;
}
};
``````

Complexity Analysis

• Time complexity : \$O(N^2*M)\$. Here M is the average size of lists .
• Space complexity : \$O(1)\$.

#### Approach #2 Heap [Accepted]

Algorithm

We can use priority_queue to save the element of the lists . Then reconstruct the list with heap .

c++

``````class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue <int , vector<int> , greater<int> > qlist ;
for( int i = 0 ; i < lists.size() ; i ++ ) {
while( lists[i] != NULL ) {
qlist.push( lists[i]->val ) ;
lists[i] = lists[i]->next;
}
}
while( qlist.size() ) {
ListNode *temp = new ListNode( qlist.top() ) ;
p->next = temp ;
p = p->next ;
qlist.pop() ;
}
}
};
``````

Complexity Analysis

• Time complexity: \$O(MNlogN)\$. When we save the element to heap will take us \$O(MNlogN)\$.
Pop operation will take us \$O(MNlogN)\$.So total time is \$O(MN+2MNlogN)\$
• Space complexity : \$O(M*N)\$.
####Approach #3 Divide and conquer[Accepted]

Algorithm

Like the merge sort . we can divide the lists to two part then merge each two lists .
and we will still use the function ( merge two lists ).

c++

``````class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* head = new ListNode(0) ;
while( l1 != NULL && l2 != NULL ) {
if( l1->val <= l2->val ) {
p->next = l1 ;
p = p->next ;
l1 = l1->next ;
}
else {
p->next = l2 ;
p = p->next ;
l2 = l2->next ;
}
}
if( l1 != NULL ) {
p->next = l1 ;
}
else if( l2 != NULL ) {
p->next = l2 ;
}
}
ListNode* divide_and_conquer(vector< ListNode* >& lists , int left , int right  ) {
if(left == right ) {
return lists[left];
}
int mid = (right - left ) / 2 + left ;
return mergeTwoLists( divide_and_conquer( lists , left , mid )  , divide_and_conquer( lists , mid + 1 ,right ) ) ;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if( lists.size() == 0 ) return NULL;
return divide_and_conquer( lists , 0 , lists.size() - 1 ) ;
}
};
``````

Complexity Analysis

• Time complexity: \$O(MNlogN)\$. Compare to the approach #1 ,we cut the lists to two parts will \$O(N)->O(logN)\$
• Space complexity : \$O(1)\$.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.