首页 > 代码库 > Merge k Sorted Lists
Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
方法一：暴力破解，1和2合并，合并后再和3合并，合并后再和4合并。。。如此下去一直将所有链表节点全部合并完。
复杂度分析，假设有k个链表，每个链表平均长度为n
1和2合并，扫描节点个数为 2n
12和3合并，扫描节点个数为 3n
123和4合并，扫描节点个数为 4n
......
123..k-1和k合并，扫描节点个数为 kn
那么总得扫描节点个数为 n(2++3+4+5+6+...+k)，时间复杂度为 O(nk2)，铁定超时
方法二：使用分治法，貌似包治百病，假设有k个链表，每个链表有n个节点，那么就将k个链表分成两部分，每部分都是k/2个链表，先合并k/2个链表，再回来合并k个链表，递推公式为 T(k) = 2T(k/2) + T(nk)，使用主定理公式 时间复杂度为 O(nklogk)
可以利用迭代的方式，例如：有链表0,1,2,3,4,5，先合并03,14,25，将结果分别存放在0,1,2中，然后再合并02，结果存在0中，最后在合并01，结果存放在0中，那么lists[0]就是所要求的，代码如下：
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 ListNode *mergeKLists(vector<ListNode *> &lists) {12 if( lists.empty() ) return NULL;13 int n = lists.size();14 while( n>1 ) {15 int k = (n+1)/2;16 for(int i=0; i<n/2; ++i)17 lists[i] = mergeLists(lists[i], lists[i+k]);18 n = k;19 }20 return lists[0];21 }22 23 ListNode* mergeLists(ListNode* lhs, ListNode* rhs) { //合并两链表24 if( !lhs ) return rhs;25 if( !rhs ) return lhs;26 ListNode node(-1);27 ListNode* pre = &node;28 while( lhs && rhs ) {29 if( lhs->val < rhs->val ) {30 pre->next = lhs;31 lhs = lhs->next;32 }33 else {34 pre->next = rhs;35 rhs = rhs->next;36 }37 pre = pre->next;38 }39 pre->next = lhs ? lhs : rhs;40 return node.next;41 }42 };
方法三：维护一个k个大小的小根堆，首先将每个链表的第一个节点push进堆中，然后进入以下循环：取堆中最小元素，放入该元素的下一个节点至对中，直至堆为空
依然假设k个链表，每个链表n个节点，那么共需要访问nk个节点，每次放入一个节点到堆中需要logk的时间，那么时间复杂度为O(nklongk)
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 struct cmp {12 bool operator()(const ListNode* lhs, const ListNode* rhs) const {13 return lhs->val > rhs->val;14 }15 };16 17 public:18 ListNode *mergeKLists(vector<ListNode *> &lists) {19 if( lists.empty() ) return NULL;20 priority_queue<ListNode*, vector<ListNode*>, cmp> pq; //构造最小堆21 for(int i=0; i<lists.size(); ++i) { //初始化，先将每个链表的第一个节点放入堆中22 if( lists[i] ) {23 pq.push(lists[i]);24 lists[i] = lists[i]->next;25 }26 }27 ListNode node(-1);28 ListNode* pre = &node;29 while( !pq.empty() ) {30 pre->next = pq.top();31 pq.pop();32 pre = pre->next;33 if( pre->next ) pq.push(pre->next); //将取出的节点的下一个节点放入堆中34 }35 pre->next = 0;36 return node.next;37 }38 };
Merge k Sorted Lists
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。