题目
描述
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
数据范围：节点总数 0≤n≤5000，每个节点的 val 满足 ∣val∣<=1000
要求：时间复杂度 O(nlogn)
示例 1
输入：[{1,2,3},{4,5,6,7}]返回值：{1,2,3,4,5,6,7}
复制代码
示例 2
输入：[{1,2},{1,4,5},{6}]返回值：{1,1,2,4,5,6}
复制代码
分析
考虑特殊情况
在进行问题分析过程前，我们先考虑一下特殊情况，那么在这道问题中，有哪些情况是特殊的呢？
不难发现，如下情况：
考虑一般情况
其实这个问题是合并两个链表的问题衍生，我们之前学习了如何合并两个有序链表，那么我们可以将这个问题进行拆解。
第一种思路，也是最容易想到的思路，对所有链表依次进行合并：
先合并第一个，第二个，得到合并后的链表；然后使用该链表来和第三个链表进行合并，依次进行。
我们假设有 n 个链表，每两个链表合并平均需要遍历 m 次，那么我们的时间复杂度就大致应该是 O(mn);
第二种思路，我们也是基于两个两个链表合并的函数，对我们拥有的 n 个链表进行拆解：
分为前半部分的链表和后半部分的链表，那最终的结果实际上是合并这两部分链表的结果；
前半部分和后半部分其实是我们的子问题，可以归并的方式获取；
最后的停止条件是我们的子区间为空返回空指针或者只有一个链表，返回该链表。
使用归并的方法就可以将使用两个链表合并操作的次数下降到 O(logn)，可以满足题目的要求。
代码示例
版本一
注意：这里 pReturn 首先赋值为 lists[0]，进行比较时从 lists[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) { if(lists.size() == 0){ return nullptr; } if(lists.size() == 1){ return lists[0]; } ListNode* pReturn = lists[0]; for(size_t i = 1;i < lists.size();++i){ pReturn = merge2Lists(pReturn, lists[i]); } return pReturn; } ListNode* merge2Lists(ListNode* pHead1, ListNode* pHead2) { // special condition if (nullptr == pHead1) { return pHead2; }
if (nullptr == pHead2) { return pHead1; }
ListNode* pReturn = nullptr; ListNode* pCur0 = nullptr; ListNode* pCur1 = pHead1; ListNode* pCur2 = pHead2;
// assign the pReturn if (pHead1->val <= pHead2->val) { pReturn = pHead1; pCur1 = pCur1->next; } else { pReturn = pHead2; pCur2 = pCur2->next; } pCur0 = pReturn;
// traverse the two list and link them while (nullptr != pCur1 && nullptr != pCur2) { if (pCur1->val <= pCur2->val) { pCur0->next = pCur1; pCur1 = pCur1->next; } else { pCur0->next = pCur2; pCur2 = pCur2->next; } pCur0 = pCur0->next; }
if (nullptr == pCur1) { pCur0->next = pCur2; } else if (nullptr == pCur2) { pCur0->next = pCur1; }
return pReturn; }};
复制代码
版本二
注意这里的终止条件：
left > right：返回 nullptr
left == right:返回 lists[left]
class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { if(lists.size() == 0){ return nullptr; } if(lists.size() == 1){ return lists[0]; } return divideMerge(lists, 0, lists.size() - 1); } ListNode* divideMerge(vector<ListNode*>& lists,int left, int right){ if(left > right){ return nullptr; }else if(left == right){ return lists[left]; } int mid = (left+right)/2; return merge2Lists(divideMerge(lists, left, mid), divideMerge(lists, mid+1, right)); } ListNode* merge2Lists(ListNode* pHead1, ListNode* pHead2) { ...// 实现同1 }};
复制代码
评论