首页 > 代码库 > Leetcode: Merge k Sorted Lists
Leetcode: Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
分析：
一个很简单的解法是调用k-1次merge two sorted linkedlist，假设每个list长度为n,那么时间复杂度为2n + 3n + .... kn = (k*(k+1)/2-1)n ~ O(n*k^2)，超时：
class Solution {public: ListNode *mergeKLists(vector<ListNode *> &lists) { if(lists.size() == 0) return NULL; ListNode *l = lists[0]; for(int i = 1; i < lists.size(); i++){ l = mergeList(l, lists[i]); } return l; } ListNode * mergeList(ListNode *l1, ListNode *l2){ if(l1 == NULL) return l2; if(l2 == NULL) return l1; ListNode *dummy = new ListNode(-1); dummy->next = NULL; for(ListNode *p = dummy; l1 || l2; p = p->next){ int l1v = l1?l1->val:INT_MAX; int l2v = l2?l2->val:INT_MAX; if(l1v <= l2v){ p->next = l1; l1 = l1->next; }else{ p->next = l2; l2 = l2->next; } } return dummy->next; }};
我们可以采用divide-conquer的思想，先将k个linked list合并成k/2个，然后重复上述过程直到只剩一个linked list。复杂度递推公式为T(k)=T(k/2)+T(n)，求解得时间复杂度为O(nklogk)。
Leetcode: Merge k Sorted Lists
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。