[LeetCode23]Merge k Sorted Lists（合并k个有序链表）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
思路：借鉴归并排序的思想，针对这个lists进行排序
假设总共有k个list，每个list的最大长度是n，那么运行时间满足递推式T(k) = 2T(k/2)+O(n*k)。根据主定理，算出总复杂度是O(nklogk)
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {if(lists.size()<=0) return NULL;return mergeKLists(lists, 0, lists.size()-1);}ListNode* mergeKLists(vector<ListNode*>& lists, int startIndex, int endIndex){if(startIndex<endIndex){int mid=(startIndex+endIndex)>>1;ListNode *l1=mergeKLists(lists, startIndex, mid);ListNode *l2=mergeKLists(lists, mid+1, endIndex);return mergeKLists(l1, l2);}else{return lists[startIndex];}}ListNode* mergeKLists(ListNode* l1, ListNode* l2){if(NULL==l1) return l2;if(NULL==l2) return l1;ListNode* dummy=new ListNode(-1), *cur=dummy;while(NULL!=l1&&NULL!=l2){if(l1->val<l2->val){cur->next=l1;l1=l1->next;cur=cur->next;}else{cur->next=l2;l2=l2->next;cur=cur->next;}}if(l1) cur->next=l1;if(l2) cur->next=l2;return dummy->next;}
};