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和B return 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); } };
小结:创作不易，点个关注支持一下吧
如果有喜欢C++的同学可以观看作者的其他专栏，全套C++都在更新(从C++基础到Linux系 统编程、网络编程 数据编程等等... 并且有一个完整C++项目)
