【力扣LeetCode】23 合并K个排序链表

本文主要是介绍【力扣LeetCode】23 合并K个排序链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述（难度难）

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

链接

https://leetcode-cn.com/problems/merge-k-sorted-lists/

思路

比较好的两种思路
1、与合并两个有序链表一样，K个链表一起从头往尾走，每次选取K个链表中指针指向位置的最小值，这个最小值使用优先队列维护较为合适。
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) {if(lists.size() == 0){return NULL;}if(lists.size() == 1){return lists[0];}if(lists.size() > 1){vector<ListNode*> liststemp;if(lists.size()%2 == 0){for(int i = 0; i < lists.size(); i+=2){ListNode* ans = mergeTwoLists(lists[i], lists[i+1]);liststemp.push_back(ans);}lists = liststemp;return mergeKLists(lists);}else{// 这里是 i < lists.size()-1 有所怀疑没有仔细确认导致浪费了一点时间查错for(int i = 0; i < lists.size()-1; i+=2){ListNode* ans = mergeTwoLists(lists[i], lists[i+1]);liststemp.push_back(ans);}liststemp.push_back(lists[lists.size()-1]);lists = liststemp;return mergeKLists(lists);}}return NULL;}ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* ans = NULL;if(l1 == NULL && l2 == NULL){return NULL;}else if(l1 == NULL){return l2;}else if(l2 == NULL){return l1;}else{ListNode* t1 = l1;ListNode* t2 = l2;if(t1->val < t2->val){ans = t1;t1 = t1->next;}else{ans = t2;t2 = t2->next;}ListNode* tans = ans;while(t1&&t2){if(t1->val < t2->val){tans->next = t1;t1 = t1->next;tans = tans->next;}else{tans->next = t2;t2 = t2->next;tans = tans->next;}}while(t1){tans->next = t1;t1 = t1->next;tans = tans->next;}while(t2){tans->next = t2;t2 = t2->next;tans = tans->next;}}return ans;}
};

debug代码：

#include <bits/stdc++.h>
using namespace std;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 NULL;}if(lists.size() == 1){return lists[0];}if(lists.size() > 1){vector<ListNode*> liststemp;if(lists.size()%2 == 0){for(int i = 0; i < lists.size(); i+=2){ListNode* ans = mergeTwoLists(lists[i], lists[i+1]);liststemp.push_back(ans);}lists = liststemp;return mergeKLists(lists);}else{for(int i = 0; i < lists.size()-1; i+=2){ListNode* ans = mergeTwoLists(lists[i], lists[i+1]);liststemp.push_back(ans);}liststemp.push_back(lists[lists.size()-1]);lists = liststemp;return mergeKLists(lists);}}return NULL;}ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* ans = NULL;if(l1 == NULL && l2 == NULL){return NULL;}else if(l1 == NULL){return l2;}else if(l2 == NULL){return l1;}else{ListNode* t1 = l1;ListNode* t2 = l2;if(t1->val < t2->val){ans = t1;t1 = t1->next;}else{ans = t2;t2 = t2->next;}ListNode* tans = ans;while(t1&&t2){if(t1->val < t2->val){tans->next = t1;t1 = t1->next;tans = tans->next;}else{tans->next = t2;t2 = t2->next;tans = tans->next;}}while(t1){tans->next = t1;t1 = t1->next;tans = tans->next;}while(t2){tans->next = t2;t2 = t2->next;tans = tans->next;}}return ans;}
};int main()
{Solution s;ListNode* l11 = new ListNode(1);ListNode* l12 = new ListNode(4);ListNode* l13 = new ListNode(5);l11->next = l12;l12->next = l13;while(l11){cout << l11->val << endl;l11 = l11->next;}ListNode* l21 = new ListNode(1);ListNode* l22 = new ListNode(3);ListNode* l23 = new ListNode(4);l21->next = l22;l22->next = l23;ListNode* l31 = new ListNode(2);ListNode* l32 = new ListNode(6);l31->next = l32;vector<ListNode*> test;test.push_back(l11);test.push_back(l21);test.push_back(l31);ListNode* ans = s.mergeKLists(test);while(ans){cout << ans->val << " ";ans = ans->next;}return 0;
}