归并排序力扣题（leetcode）
归并排序力扣题（leetcode）23. 合并 K 个升序链表
难度：困难
相关标签：链表、分治、堆（优先队列）、归并排序
题目：
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1:
输入：lists = [,,]
输出：
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6示例 2:
输入：lists = []
输出：[]示例 3:
输入：lists = [[]]
输出：[]提示：
<ul>\(k == lists.length\)
\(0 next; } if(left != nullptr)curPtr->next = left; if(right != nullptr)curPtr->next = right; // 返回排序后的链表头 return newNodePtr->next; } // 分治归并 ListNode* merge(vector& lists, int l, int r) { if(l == r)return lists; if(l > r)return nullptr; int mid = (l+r)/2; ListNode* left = merge(lists, l, mid); ListNode* right = merge(lists, mid+1, r); return mergeList(left, right); } // 主函数入口 ListNode* mergeKLists(vector& lists) { if(lists.empty())return nullptr; return merge(lists, 0, lists.size()-1); }};相似题目
合并两个有序链表简单
丑数 II中等
按位或最大的最小子数组长度中等
148. 排序链表
难度：中等
相关标签：链表、双指针、分治、排序、归并排序
题目：
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1:
/**
* 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(nullptr) {}
* };
*/
class Solution
{
public:
ListNode* mergeList(ListNode* left, ListNode* right)
{
// 虚拟头节点
ListNode* newNodePtr = new ListNode(-1);
ListNode* curPtr = newNodePtr;
// 双指针归并（和数组归并逻辑完全一致）
while(left != nullptr && right != nullptr)
{
if(left->val <= right->val)
{
curPtr->next = left;
left = left->next;
}
else
{
curPtr->next = right;
right = right->next;
}
curPtr = curPtr->next;
}
if(left != nullptr)curPtr->next = left;
if(right != nullptr)curPtr->next = right;
// 返回排序后的链表头
return newNodePtr->next;
}
// 分治归并
ListNode* merge(vector<ListNode*>& lists, int l, int r)
{
if(l == r)return lists;
if(l > r)return nullptr;
int mid = (l+r)/2;
ListNode* left = merge(lists, l, mid);
ListNode* right = merge(lists, mid+1, r);
return mergeList(left, right);
}
// 主函数入口
ListNode* mergeKLists(vector<ListNode*>& lists)
{
if(lists.empty())return nullptr;
return merge(lists, 0, lists.size()-1);
}
};示例 2:
输入：head =
输出：示例 3:
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]提示：
<ul>链表中节点的数目在范围 $ $内
\(-10^5 > 1; merge_sort(q, l, mid); merge_sort(q, mid + 1, r); int i = l, j = mid + 1, k = 0; while (i
页:
[1]