网站内容编辑,做网站搭建环境,哈尔滨公司网页制作,自己做的网站别人题目
给你一个链表数组#xff0c;每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中#xff0c;返回合并后的链表。
示例 #xff1a; 输入#xff1a;lists [[1,4,5],[1,3,4],[2,6]] 输出#xff1a;[1,1,2,3,4,4,5,6] 解释#xff1a;链表数组如下每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中返回合并后的链表。
示例 输入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(vectorListNode* lists) {if (lists.empty()) {return nullptr;}return merge(lists, 0, lists.size() - 1);}private:ListNode* merge(vectorListNode* 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;}}
};
