Merge k Sorted Lists
Total Accepted: 82424 Total Submissions: 354076 Difficulty: Hard
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Subscribe to see which companies asked this question
Hide Tags Divide and Conquer Linked List Heap Hide Similar Problems (E) Merge Two Sorted Lists (M) Ugly Number II
思路:
归并排序,与数组归并排序类似
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0) return NULL;
return mergeSort(lists, 0, lists.size()-1);
}
ListNode *mergeSort(vector<ListNode*>& lists, int s, int e){
if(s==e) return lists[s];
else {
int mid = (s + e)>>1;
ListNode *l1 = mergeSort(lists, s, mid);
ListNode *l2 = mergeSort(lists, mid+1, e);
return merge(l1,l2);
}
}
ListNode *merge(ListNode *l1, ListNode *l2){
if(l1==NULL) return l2;
if(l2==NULL) return l1;
ListNode dummy(0); // 伪头结点
ListNode *p = &dummy;
while(l1 && l2){
if(l1->val < l2->val){
p->next = l1;
l1=l1->next;
}
else {
p->next = l2;
l2=l2->next;
}
p = p->next;
}
p->next = l1!=NULL?l1:l2;
return dummy.next;
}
};