归并排序力扣题（leetcode）

归并排序力扣题（leetcode）

23. 合并 K 个升序链表

难度：困难
相关标签：链表、分治、堆（优先队列）、归并排序
题目：

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1:

1. 输入：lists = [[1,4,5],[1,3,4],[2,6]]
2. 输出：[1,1,2,3,4,4,5,6]
3. 解释：链表数组如下：
4. [
5.   1->4->5,
6.   1->3->4,
7.   2->6
8. ]
9. 将它们合并到一个有序链表中得到。
10. 1->1->2->3->4->4->5->6

复制代码

示例 2:

1. 输入：lists = []
2. 输出：[]

复制代码

示例 3:

1. 输入：lists = [[]]
2. 输出：[]

复制代码

提示：
<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[l];        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);    }};[/code]相似题目

合并两个有序链表简单
丑数 II中等
按位或最大的最小子数组长度中等
148. 排序链表

难度：中等
相关标签：链表、双指针、分治、排序、归并排序
题目：

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1:

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     ListNode *next;
6. *     ListNode() : val(0), next(nullptr) {}
7. *     ListNode(int x) : val(x), next(nullptr) {}
8. *     ListNode(int x, ListNode *next) : val(x), next(nullptr) {}
9. * };
10. */
11. class Solution
12. {
13. public:
14.     ListNode* mergeList(ListNode* left, ListNode* right)
15.     {
16.         // 虚拟头节点
17.         ListNode* newNodePtr = new ListNode(-1);
18.         ListNode* curPtr = newNodePtr;
20.         // 双指针归并（和数组归并逻辑完全一致）
21.         while(left != nullptr && right != nullptr)
22.         {
23.             if(left->val <= right->val)  
24.             {
25.                 curPtr->next = left;
26.                 left = left->next;
27.             }
28.             else
29.             {
30.                 curPtr->next = right;
31.                 right = right->next;
32.             }
33.             curPtr = curPtr->next;
34.         }
36.         if(left != nullptr)  curPtr->next = left;
37.         if(right != nullptr)  curPtr->next = right;
39.         // 返回排序后的链表头
40.         return newNodePtr->next;
41.     }
43.     // 分治归并
44.     ListNode* merge(vector<ListNode*>& lists, int l, int r)
45.     {
46.         if(l == r)  return lists[l];
47.         if(l > r)  return nullptr;
48.         int mid = (l+r)/2;
49.         ListNode* left = merge(lists, l, mid);
50.         ListNode* right = merge(lists, mid+1, r);
51.         return mergeList(left, right);
52.     }
54.     // 主函数入口
55.     ListNode* mergeKLists(vector<ListNode*>& lists)
56.     {
57.         if(lists.empty())  return nullptr;
58.         return merge(lists, 0, lists.size()-1);
59.     }
60. };

复制代码

示例 2:

1. 输入：head = [4,2,1,3]
2. 输出：[1,2,3,4]

复制代码

示例 3:

1. 输入：head = [-1,5,3,4,0]
2. 输出：[-1,0,3,4,5]

复制代码

提示：
<ul>链表中节点的数目在范围 $[0, 5 * 10^4] $内
\(-10^5 > 1;        merge_sort(q, l, mid);        merge_sort(q, mid + 1, r);        int i = l, j = mid + 1, k = 0;        while (i