厦门易尔通做网站怎么样,企业网站规划书,流量网站制作,wordpress 版面LeetCode-23 合并 K 个升序链表
给你一个链表数组#xff0c;每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中#xff0c;返回合并后的链表。
示例 1#xff1a;
输入#xff1a;lists [[1,4,5],[1,3,4],[2,6]]
输出#xff1a;[1,1,2,3,4,4,5,6]
解…LeetCode-23 合并 K 个升序链表
给你一个链表数组每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中返回合并后的链表。
示例 1
输入lists [[1,4,5],[1,3,4],[2,6]]
输出[1,1,2,3,4,4,5,6]
解释链表数组如下
[1-4-5,1-3-4,2-6
]
将它们合并到一个有序链表中得到。
1-1-2-3-4-4-5-6示例 2
输入lists []
输出[]示例 3
输入lists [[]]
输出[]提示
k lists.length0 k 10^40 lists[i].length 500-10^4 lists[i][j] 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4
solution
采用分治法
从pre_vec合并两个相邻的链表并将结果放入vec中pre_vecvec,vec.clear()循环上述操作直至pre_vec的长度为1输出pre_vec[0]
#include vectorusing namespace std;//Definition for singly-linked list.
struct ListNode {int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};//leetcode submit region begin(Prohibit modification and deletion)
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
private:ListNode *mergeLists(ListNode *A, ListNode *B) {ListNode *L new ListNode(), *P_A A, *P_B B, *cur L;while (P_A ! nullptr P_B ! nullptr) {if (P_A-val P_B-val) {ListNode *P new ListNode(P_A-val);cur-next P;cur cur-next;P_A P_A-next;} else {ListNode *P new ListNode(P_B-val);cur-next P;cur cur-next;P_B P_B-next;}}if (P_A! nullptr) {cur-next P_A;}if (P_B! nullptr) {cur-next P_B;}return L-next;}public:ListNode *mergeKLists(vectorListNode * lists) {vectorListNode * pre_vec lists;vectorListNode * vec;if (lists.size()0){return nullptr;}else if (lists.size()1){return lists[0];}do {for (int i 0; i pre_vec.size(); i 2) {if (i 1 pre_vec.size()) {vec.push_back(mergeLists(pre_vec[i], pre_vec[i 1]));} else {vec.push_back(pre_vec[pre_vec.size() - 1]);}}pre_vec vec;vec.clear();} while (pre_vec.size() ! 1);return pre_vec[0];}
};
//leetcode submit region end(Prohibit modification and deletion)ListNode *createList(int a[], int n) {ListNode *A new ListNode(), *cur A;for (int i 0; i n; i) {ListNode *p new ListNode(a[i]);p-next NULL;cur-next p;cur cur-next;}return A-next;
}int main() {int a[3] {1, 4, 5}, b[3] {1, 3, 4}, c[2] {2, 3}, na 3, nb 3, nc 2;vectorListNode * A {createList(a, na), createList(b, nb), createList(c, nc)};Solution solution;solution.mergeKLists(A);}
