23、 合并K个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
提示：
k == lists.length- $0 <= k <= 10^4$
0 <= lists[i].length <= 500- $-10^4 <= lists[i][j] <= 10^4$
lists[i]按 升序 排列lists[i].length的总和不超过 $10^4$
C++ 基础方法两两合并
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* merge(ListNode* p1,ListNode* p2) {
// 创建新的头节点
ListNode* head = new ListNode(0);
ListNode* p = head;
// 循环合并
while (p1 != nullptr && p2 != nullptr) {
if (p1->val <= p2->val){
p->next = p1;
p1 = p1->next;
} else {
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
// 合并剩余部分
if (p1 != nullptr) {
p->next = p1;
}else if (p2 != nullptr){
p->next = p2;
}
ListNode* t = head->next;
delete head;
return t;
}
// 两两归并
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.size() == 0) return nullptr;
ListNode* head = lists[0];
for (int i = 1;i < lists.size(); ++i) {
head = merge(head,lists[i]);
}
return head;
}
};
C++ 基础方法两两合并优化，二分归并思想
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* merge(ListNode* p1,ListNode* p2) {
// 创建新的头节点
ListNode* head = new ListNode(0);
ListNode* p = head;
// 循环合并
while (p1 != nullptr && p2 != nullptr) {
if (p1->val <= p2->val){
p->next = p1;
p1 = p1->next;
} else {
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
// 合并剩余部分
if (p1 != nullptr) {
p->next = p1;
}else if (p2 != nullptr){
p->next = p2;
} else {
p->next = nullptr;
}
ListNode* t = head->next;
delete head;
return t;
}
// 两两递归归并
ListNode* mergeKListsCore(vector<ListNode*>& lists,int l,int r) {
if (l == r -1) {
return merge(lists[l],lists[r]);
} else if (l >= r) {
return lists[l];// 可能会出先单个链表
}
int mid = (l+r)>>1;
ListNode* t1 = mergeKListsCore(lists,l,mid);
ListNode* t2 = mergeKListsCore(lists,mid + 1,r);
return merge(t1,t2);
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
int len = lists.size();
if (len == 1) return lists[0];
if (len >= 2) {
return mergeKListsCore(lists,0,len - 1);
}
return nullptr;
}
};
一位小伙伴的分治思想的精简C++实现
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists, int begin, int end) {
if (end < begin) return NULL;
if (end == begin) return lists[begin];
int mid = (begin + end) / 2;
auto p1 = mergeKLists(lists, begin, mid);
auto p2 = mergeKLists(lists, mid + 1, end);
ListNode head(0);
ListNode* cur = &head;
while (p1 && p2) {
if (p1->val < p2->val) {
cur->next = p1;
p1 = p1->next;
} else {
cur->next = p2;
p2 = p2->next;
}
cur = cur->next;
}
if (p1) cur->next = p1;
else if (p2) cur->next = p2;
return head.next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
return mergeKLists(lists, 0, lists.size() - 1);
}
};
// 作者：dpapa
// 链接：https://leetcode-cn.com/problems/two-sum/solution/c-gui-bing-shi-xian-by-dpapa/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
一位小伙伴的分治思想的精简C实现
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
struct ListNode head;
struct ListNode *p, *q;
if (!l1) {
return l2;
}
if (!l2) {
return l1;
}
/* 建立新的头结点 指向L1 */
head.next = l1;
l1 = &head;
/* 遍历l2节点 */
while (l2) {
p = l1->next;
q = l2->next;
if (!l1->next) {
l1->next = l2;
break;
}
if (p->val >= l2->val) {
l1->next = l2;
l2->next = p;
l2 = q;
}
l1 = l1->next;
}
return head.next;
}
struct ListNode* _mergeKLists(struct ListNode** lists, int listsSize)
{
int count;
struct ListNode* l1, *l2;
count = listsSize;
if (count == 0) {
return NULL;
} else if (count == 1) {
return lists[0];
} else if (count == 2) {
return mergeTwoLists(lists[0], lists[1]);
}
l1 = _mergeKLists(&lists[0], (count+1)/2);
l2 = _mergeKLists(&lists[(count+1)/2], count - (count+1)/2);
return mergeTwoLists(l1, l2);
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{
return _mergeKLists(lists, listsSize);
}
// 作者：wangyuanzhengbighead
// 链接：https://leetcode-cn.com/problems/two-sum/solution/cshi-xian-nlgnxiao-lu-chao-guo-90-by-wangyuanzheng/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
一位小伙伴的简单暴力解法，问题转化思想
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 将链表加入到动态数组中
vector<ListNode*> longList;
for (ListNode* start:lists){
ListNode* ptr = start;
while (ptr != NULL){
longList.push_back(ptr);
ptr = ptr->next;
}
}
// 排序
std::sort(longList.begin(),longList.end(),[](auto x,auto y){return ((x->val) < (y->val));});
// 将节点连接起来
if (longList.size() ==0){return NULL;}
for (size_t i=0;i<longList.size()-1;i++){
longList[i]->next = longList[i+1];
}
longList[longList.size()-1]->next = NULL;
return longList[0];
}
// 作者：w5LCyMOoza
// 链接：https://leetcode-cn.com/problems/two-sum/solution/chao-jian-dan-suan-fa-stdsortgao-ding-by-w5lcymooz/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
java版本
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode head : lists)
if (head != null)
pq.offer(head);
ListNode dummy = new ListNode(); // 哨兵节点，作为合并后链表头节点的前一个节点
ListNode cur = dummy;
while (!pq.isEmpty()) { // 循环直到堆为空
ListNode node = pq.poll(); // 剩余节点中的最小节点
if (node.next != null) // 下一个节点不为空
pq.offer(node.next); // 下一个节点有可能是最小节点，入堆
cur.next = node; // 合并到新链表中
cur = cur.next; // 准备合并下一个节点
}
return dummy.next; // 哨兵节点的下一个节点就是新链表的头节点
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
