LeetCode 23. 合并K个升序链表（优先队列，分治合并）

2020年9月4日 周五 天气晴 【不悲叹过去，不荒废现在，不惧怕未来】

---

本文目录

1. 优先队列2. 分治合并2.1 递归法2.2 迭代法

---

这道题有点类似归并排序。

1. 优先队列

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: // 对新的数据类型的"<"进行重写 struct cmp{ bool operator()(ListNode *a,ListNode *b){ return a->val > b->val; } }; ListNode* mergeKLists(vector<ListNode*>& lists) { // 1.所有链表的头结点加入最小堆 priority_queue<ListNode*, vector<ListNode*>, cmp> pq; for(auto h:lists){ if(h!=NULL) pq.push(h); } // 2.不断串接当前值最小的结点 ListNode* preHead = new ListNode(-1); ListNode* cur = preHead; while(!pq.empty()){ cur->next = pq.top(); pq.pop(); cur = cur->next; if(cur->next) pq.push(cur->next); } // 3.返回最终结果 return preHead->next; } }; 时间复杂度：考虑优先队列中的元素不超过 $k$ 个，那么插入和删除的时间代价为 $O\left(logk\right)$，这里最多有 $n$ 个点，对于每个点都被插入删除各一次，故总的时间代价即渐进时间复杂度为 $O\left(nlogk\right)$。空间复杂度：这里用了优先队列，优先队列中的元素不超过 $k$ 个，故渐进空间复杂度为 $O\left(k\right)$。

2. 分治合并

分治合并也就是两两进行合并。

2.1 递归法

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { // 返回最终结果 return merge(lists,0,lists.size()-1); } ListNode* merge(vector<ListNode*>& lists, int left, int right){ if(left < right){ int mid = left + (right - left) / 2; ListNode* l_list = merge(lists,left,mid); // 合并后的左部分链表 ListNode* r_list = merge(lists,mid+1,right); // 合并后的右部分链表 return mergeTwoLists(l_list,r_list); // 合并左右部分链表 } else if(left > right) return nullptr; // lists为空的情况 else return lists[left]; // 递归到单个链表，返回它 } // 合并两个有序链表 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){ ListNode* dummyHead = new ListNode(-1), *tail = dummyHead; while(l1 && l2){ if(l1->val < l2->val){ tail->next = l1; l1 = l1->next; } else{ tail->next = l2; l2 = l2->next; } tail = tail->next; } tail->next = l1?l1:l2; return dummyHead->next; } };

2.2 迭代法

迭代法合并的过程类似于归并排序。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { int len = lists.size(); if(len == 0) return nullptr; // 以下过程仿照“归并排序” for(int seg = 1; seg < len; seg *= 2){ // seg：1，2，4，8... for(int beg = 0; beg < len; beg += seg*2){ // l为左部分链表的头结点索引，r为右部分链表的头结点索引 int l = beg, r = l + seg; // 合并后链表的头结点保存在索引l处 if(r < len) lists[l] = mergeTwoLists(lists[l],lists[r]); } } // 返回最终结果 return lists[0]; } // 合并两个有序链表 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){ ListNode* dummyHead = new ListNode(-1), *tail = dummyHead; while(l1 && l2){ if(l1->val < l2->val){ tail->next = l1; l1 = l1->next; } else{ tail->next = l2; l2 = l2->next; } tail = tail->next; } tail->next = l1?l1:l2; return dummyHead->next; } }; 时间复杂度：$O\left(nlogk\right)$。假设共有 $n$ 个结点，每次合并都要遍历所有结点。一共有 $k$ 个链表，最后合并成一个，要遍历 $logk$ 次。所以最终的时间复杂度为 $O\left(nlogk\right)$。空间复杂度：递归：$O\left(logk\right)$，迭代：$O\left(1\right)$。