首页 > 代码库 > leetcode第22题--Merge k Sorted Lists
leetcode第22题--Merge k Sorted Lists
problem：Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
先合并两个list，再根据归并排序的方法递归合并。假设总共有k个list，每个list的最大长度是n，那么运行时间满足递推式T(k) = 2T(k/2)+O(n*k)。根据主定理，可以算出算法的总复杂度是O(nklogk)。空间复杂度的话是递归栈的大小O(logk)。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) // 将两个list merge{ if(!l1) return l2; if(!l2) return l1; ListNode *tmp = new ListNode(0); ListNode *ans = tmp; while(l1 && l2) { if(l1 -> val < l2 -> val) { ans -> next = l1; ans = ans -> next; l1 = l1 -> next; } else { ans -> next = l2; ans = ans -> next; l2 = l2 -> next; } } if (l1) { while(l1) { ans -> next = l1; ans = ans -> next; l1 = l1 -> next; } } if (l2) { while(l2) { ans -> next = l2; ans = ans -> next; l2 = l2 -> next; } } ans = tmp; delete ans; return tmp -> next;}ListNode *reMerge(vector<ListNode *> &lists, int l, int r){ if(l < r) // 类似于归并排序，把一大块分成l和r两块，然后将两个合并（l和r也还可以再分） { int m = (l + r)/2; return mergeTwoLists(reMerge(lists, l, m), reMerge(lists, m + 1, r)); } else return lists[l];}ListNode *mergeKLists(vector<ListNode *> &lists){ ListNode *ans = NULL;// 用NULL 而不是利用 new ListNode(0) if (lists.size() == 0) return ans; return reMerge(lists, 0, lists.size() - 1);}};
leetcode第22题--Merge k Sorted Lists
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。