合并k个已排序的链表

article/2025/10/2 13:04:07

ojbk...开始以为这题没有内存要求,所以就用来一个很简单的方法合并。创建第三条链表，结果部分案例过不去。

这个代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* mergetK(ListNode *A,ListNode *B){ListNode *C = nullptr;ListNode *ans = nullptr;while(A != nullptr && B != nullptr){ListNode *s = new ListNode(0);if(A->val > B->val){s->val = B->val;s->next = nullptr;B = B->next;}else{s->val = A->val;s->next = nullptr;A = A->next;}if(C == nullptr){C = s;ans = C;}else{C->next = s;C = C->next;}}while(A != nullptr){ListNode *s = new ListNode(0);s->val = A->val;s->next = nullptr;if(C == nullptr){C = s;ans = C;}else{C->next = s;C = C->next;}A = A->next;}while(B != nullptr){ListNode *s = new ListNode(0);s->val = B->val;s->next = nullptr;if(C == nullptr){C = s;ans = C;}else{C->next = s;C = C->next;}B = B->next;}return ans;}ListNode *mergeKLists(vector<ListNode *> &lists) {if(lists.empty()){return nullptr;}ListNode *ans;ans = lists[0];for(int i=1;i<lists.size();i++){ans = mergetK(ans,lists[i]);}return ans;}
};

好吧，看来不能创建新的节点，只能用辅助指针了。。。。。(这题就是合并两个有序链表，水题)

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* mergetK(ListNode *A,ListNode *B){ListNode *pA = A;ListNode *pB = B;ListNode *ans = nullptr;ListNode *head = nullptr;while(A != nullptr && B != nullptr){if(A->val <= B->val){if(ans == nullptr){ans = A;head = A;}else{head->next = A;head = head->next;}//pA = A;A = A->next; }else{if(ans == nullptr){ans = B;head = B;}else{head->next = B;head = head->next;}//pB = B;B = B->next;}}if(A != nullptr){head->next = A;}if(B != nullptr){head->next = B;}return ans;}ListNode *mergeKLists(vector<ListNode *> &lists) {if(lists.empty()){return nullptr;}ListNode *ans;ans = lists[0];for(int i=1;i<lists.size();i++){if(lists[i] == nullptr){continue;}ans = mergetK(ans,lists[i]);}return ans;}
};

我去，超时.....

看来这题没有想的那么简单呀....

分析下代码的时间复杂度，，，，

遍历 litsts O(n)

内部:等于遍历了一遍链表 O(n+m)

这么算:O(n^2)

看题目要求的是时间复杂度 O(nlogk)

k是链表的个数：说明只能从遍历 litsts开🔪了。。。。

根据经验，合并两个有序链表时间复杂度最优 O(n+m) 再一次说明只能从遍历 litsts优化了

等等，logK对数时间，第一反应应该是二分吧。我去，说不定可以解决

二分的前提：保证有序，nice，题目的条件刚好是有序的(因为数组下标是递增的呀)

优化后：

我操，终于过了。。。。。感动，落泪。一个小时呜呜....

两个链表的合并:（前面的代码有点小bug,有一种情况需要特殊处理）

当一个链表尾空时:(此时应该不需要合并)

[{-9},{},{-10,-8,-2,-1,2},{-10,-9,-7,-6,-5,-2,-2,1,4},{-7,-7,-1,0,4},{},{-4,0},{-9,-6,-5,-5,-2,2,3,3}]

更改:做个特判，两个有序链表的合并就不说了，只要你认真一点就一定能写出来。

合并两个有序链表代码:

struct ListNode 
{int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};ListNode* merge(ListNode *A,ListNode *B)
{//特判 (A=nullptr && B=nullptr) 或者// (A=nullptr && B!=nullptr) 或者 (A!=nullptr && B=nullptr)if(A == nullptr || B == nullptr){return A==nullptr ? B:A;}ListNode *head = nullptr;ListNode *ans  = nullptr;while(A != nullptr && B != nullptr){if(A->val <= B->val){if(ans == nullptr){ans = A;head = A;}else{head->next = A;head = head->next;}A = A->next;}else{if(ans == nullptr){ans = B;head = B;}else{head->next = B;head = head->next;}B = B->next;}}if(A != nullptr){head->next = A;}if(B != nullptr){head->next = B;}retrun ans;
}

二分的思路及代码：

对于二分有两种方法:递归(推荐使用) 非递归

通常我们使用递归就行，好分析，好写代码

我们先看一个例子来分析:

先分成两半: A和B的处理过程一定要是一样的(或者说将一个整体划分为两个与这个整体相同的子问题)

假设将A和B成最小的子问题了，此时我们应该干嘛？？？？

当然是进行链表合并咯。。。。

好的我们来合并吧，又看，A和B还没划分到最小呀。(递归是一个自顶向下的过程)

为什么我这里说要把A和B看作最小的子问题呢？？这个是作者对递归的特别理解吧，如果画出解空间，递归是不是需要回溯，当我们回溯到这一层的时候是不是需要合并 A和B.

ok....为了方便理解我们不妨就把每次状态都当作最小问题，对于最小问题的求解什么样的，我们就怎么处理就行了，而且本来就数划分为与子问题一样的问题吗，只是规模遍历而已。

我们继续划分

我们写代码吧(二分代码)

//返回值看我上面画的图
ListNode* binary_lists(vector<ListNode *> &lists,int l,int r)
{//先写边界条件(出口)if(l == r){return lists[l];}if(l > r){return nullptr;}   int mid = (l+r)/2;//合并 A和B    因为回溯到这个点的时候需要合并A和Breturn merge(binary_lists(lists,l,mid),binary_lists(lists,mid+1,r));}

okk...

我们把所有的代码合在一起吧

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *ans1;ListNode* merget(ListNode *A,ListNode *B){if(A == nullptr || B == nullptr){return A == nullptr ? B:A;}ListNode *pA = A;ListNode *pB = B;ListNode *ans = nullptr;ListNode *head = nullptr;while(A != nullptr && B != nullptr){if(A->val <= B->val){if(ans == nullptr){ans = A;head = A;}else{head->next = A;head = head->next;}//pA = A;A = A->next; }else{if(ans == nullptr){ans = B;head = B;}else{head->next = B;head = head->next;}//pB = B;B = B->next;}}if(A != nullptr){head->next = A;}if(B != nullptr){head->next = B;}return ans;}ListNode* merList(vector<ListNode *> &lists,int l,int r){if(l == r)    //只有一条{return lists[l];}if( l > r){return nullptr;}int mid = (l + r)/2;return merget(merList(lists,l,mid),merList(lists,mid+1,r));}ListNode *mergeKLists(vector<ListNode *> &lists) {if(lists.empty()){return nullptr;}//       ans = lists[0];
//         for(int i=1;i<lists.size();i++)
//         {
//            if(lists[i] == nullptr)
//            {
//                continue;
//            }
//            ans = mergetK(ans,lists[i]);
//         }        return merList(lists,0,lists.size()-1);}
};