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

#xff1a;

要将多个已按升序排列的链表合并成一个升序链表可以使用分治法的思想。

我们利用分治法的思想递归地将链表数组拆分成两部分然后合并这些部分最终得到一个合并后的升序链表。

定义一个辅助函数mergeTwoLists(ListNode*

list1,

list2)用于合并两个链表的方法这是我们之前讨论过的合并两个升序链表的方法。

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

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

具体步骤如下

计算链表数组的中间位置mid将链表数组拆分成两部分左半部分为[0,

mid-1]右半部分为[mid,

size-1]。

递归调用mergeKLists函数分别对左右两部分进行合并得到leftList和rightList。

最终再调用mergeTwoLists方法将leftList和rightList合并为一个新的升序链表并返回合并后的结果。

Code