首页 > 代码库 > [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个有序的链表进行归并排序。并分析其复杂度。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* merge(ListNode* left, ListNode* right){ //归并操作 if(left==NULL) return right; if(right==NULL) return left; ListNode *ans =new ListNode(0); if(left->val <= right->val){ ans=left; left = left->next; }else{ ans=right; right=right->next; } ans->next = merge(left,right); return ans; } ListNode* mergesort(vector<ListNode *> &lists,int left,int right){ //devide && conquer if(left>right){ return NULL; }if(left==right){ return lists[left]; }else{ int middle = (left+right)>>1; ListNode *lleft = mergesort(lists,left,middle); ListNode *lright = mergesort(lists,middle+1,right); return merge(lleft,lright); } } ListNode *mergeKLists(vector<ListNode *> &lists) { int left =0,right =lists.size()-1; int middle= (left+right)>>1; ListNode *lleft = mergesort(lists,left,middle); ListNode *lright = mergesort(lists,middle+1,right); return merge(lleft,lright); }};
时间复杂度： O(n*logn)
空间复杂度： O(1)
至于具体的量化分析呢，呵呵。。。数学推导了
转载请注明出处： http://www.cnblogs.com/double-win/ 谢谢！
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。