【LeetCode 23】合并K个排序链表
2023-09-14 09:03:43 时间
【题解】
会归并排序吧? 就把这K个链表当成是K个数字就好。 然后做归并排序。 因为归并排序的时候本来就会有这么一个过程。 [l..mid]和[mid+1..r]这两段区间都是有序的了已经。 然后再把他们俩合并起来。 合并起来之后把这个链表直接放在这个区间的最左边那个位置就好 上一级的合并要用的时候就直接取这个区间最左边那个链表。 有个人关于时间复杂度的证明说的挺好的贴一下 ![](https://img2018.cnblogs.com/blog/1251265/201911/1251265-20191109164330161-1268340088.png)【代码】
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void merge(vector<ListNode*> &lists,int l,int r){
if (l>=r) return;
int mid = (l+r)>>1;
merge(lists,l,mid);merge(lists,mid+1,r);
ListNode *temp = (ListNode *) malloc(sizeof(ListNode));
temp->next =NULL;
ListNode *p = temp;
ListNode *p1 = lists[l],*p2 = lists[mid+1];
while(p1 && p2){
if (p1->val<p2->val){
p->next = p1;
p1 = p1->next;
}else{
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
if (p2) p1 = p2;
while (p1){
p->next = p1;
p = p->next;
p1 = p1->next;
}
lists[l] = temp->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return NULL;
int n = lists.size();
merge(lists,0,n-1);
return lists[0];
}
};
相关文章
- Java实现 LeetCode 747 至少是其他数字两倍的最大数(暴力)
- Java实现 LeetCode 706 设计哈希映射(数组+链表)
- Java实现 LeetCode 206 反转链表
- Java实现 LeetCode 203 移除链表元素
- Java实现 LeetCode 190 颠倒二进制位
- Java实现 LeetCode 148 排序链表
- Java实现 LeetCode 143 重排链表
- Java实现 LeetCode 109 有序链表转换二叉搜索树
- Java实现 LeetCode 92 反转链表 II
- Java实现 LeetCode 83 删除排序链表中的重复元素
- Java实现 LeetCode 24 两两交换链表中的节点
- Java实现 LeetCode 23 合并K个排序链表
- 【LeetCode 24】两两交换链表中的节点
- leetCode 82.Remove Duplicates from Sorted List II (删除排序链表的反复II) 解题思路和方法
- Leetcode 326. 3 的幂
- 【Leetcode刷题Python】25.K 个一组翻转链表
- LeetCode 25. K 个一组翻转链表
- LeetCode 83. 删除排序链表中的重复元素
- 【21】合并两个有序链表 【LeetCode】