题目:

题解：

class Solution {// 21. 合并两个有序链表ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {auto dummy = new ListNode(); // 用哨兵节点简化代码逻辑auto cur = dummy; // cur 指向新链表的末尾while (list1 && list2) {if (list1->val < list2->val) {cur->next = list1; // 把 list1 加到新链表中list1 = list1->next;} else { // 注：相等的情况加哪个节点都是可以的cur->next = list2; // 把 list2 加到新链表中list2 = list2->next;}cur = cur->next;}cur->next = list1 ? list1 : list2; // 拼接剩余链表return dummy->next;}// 合并从 lists[i] 到 lists[j-1] 的链表ListNode *mergeKLists(vector<ListNode *> &lists, int i, int j) {int m = j - i;if (m == 0) return nullptr; // 注意输入的 lists 可能是空的if (m == 1) return lists[i]; // 无需合并，直接返回auto left = mergeKLists(lists, i, i + m / 2); // 合并左半部分auto right = mergeKLists(lists, i + m / 2, j); // 合并右半部分return mergeTwoLists(left, right); // 最后把左半和右半合并}public:ListNode *mergeKLists(vector<ListNode *> &lists) {return mergeKLists(lists, 0, lists.size());}
};