LeetCode23.合并K个升序链表

题目

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 ：

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

思路

要将多个已按升序排列的链表合并成一个升序链表，可以使用分治法的思想。我们利用分治法的思想，递归地将链表数组拆分成两部分，然后合并这些部分，最终得到一个合并后的升序链表。

• 定义一个辅助函数mergeTwoLists(ListNode* list1, ListNode* list2)，用于合并两个链表的方法，这是我们之前讨论过的合并两个升序链表的方法。

• 在mergeKLists函数中，首先判断输入的链表数组是否为空，如果为空则返回nullptr。

• 利用分治法的思想，将链表数组不断地拆分成两部分，然后递归地合并这些部分，直到只剩下一个链表为止。具体步骤如下：

  • 计算链表数组的中间位置mid，将链表数组拆分成两部分：左半部分为[0, mid-1]，右半部分为[mid, size-1]。
  • 递归调用mergeKLists函数，分别对左右两部分进行合并，得到leftList和rightList。
  • 最终，再调用mergeTwoLists方法将leftList和rightList合并为一个新的升序链表，并返回合并后的结果。

• 最终返回合并后的链表即可。

Code：

class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {if (lists.empty()) {return nullptr;}return merge(lists, 0, lists.size() - 1);}private:ListNode* merge(vector<ListNode*>& lists, int left, int right) {if (left == right) {return lists[left];}if (left < right) {int mid = left + (right - left) / 2;ListNode* leftList = merge(lists, left, mid);ListNode* rightList = merge(lists, mid + 1, right);return mergeTwoLists(leftList, rightList);}return nullptr;}ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (!list1) {return list2;}if (!list2) {return list1;}if (list1->val < list2->val) {list1->next = mergeTwoLists(list1->next, list2);return list1;} else {list2->next = mergeTwoLists(list1, list2->next);return list2;}}
};