LeetCode 23. 合并 K 个升序链表（分治 + 链表归并）

LeetCode 23. 合并 K 个升序链表分治 链表归并一、题目描述给你一个链表数组每个链表都已经按照升序排列请将所有链表合并成一条升序链表并返回合并后的链表头节点。示例输入 lists[[1,4,5],[1,3,4],[2,6]]输出[1,1,2,3,4,4,5,6]二、最容易想到的方法最直接的方法是顺序合并先合并第1条和第2条链表 再和第3条链表合并 再和第4条链表合并……假设一共有 k 条链表每条链表平均长度为 n时间复杂度O(k²n)当链表数量较多时效率比较低。三、最优思路分治归并排序思想归并排序的核心思想大问题拆成小问题小问题解决后再合并。例如L1 L2 L3 L4 L5 L6先拆成L1 L2 L3 L4 L5 L6继续拆L1 L2 L3 L4 L5 L6最后不断合并(L1L2) (L3) (L4L5) (L6)最终得到整个结果。四、子问题合并两个升序链表这是经典题《合并两个有序链表》的做法。核心思路两个指针分别指向两条链表每次选择较小节点接到结果链表后面某条链表遍历结束后直接把另一条链表剩余部分接到尾部。代码defmergeTwoLists(l1,l2):dummyListNode()curdummywhilel1andl2:ifl1.vall2.val:cur.nextl1 l1l1.nextelse:cur.nextl2 l2l2.nextcurcur.nextifl1:cur.nextl1else:cur.nextl2returndummy.next五、分治递归定义递归函数merge(left,right)表示合并lists[left:right1]区间内所有链表。终止条件ifleftright:returnlists[left]递归拆分mid(leftright)//2left_listmerge(left,mid)right_listmerge(mid1,right)returnmergeTwoLists(left_list,right_list)六、完整代码fromtypingimportList,OptionalclassSolution:defmergeKLists(self,lists:List[Optional[ListNode]])-Optional[ListNode]:ifnotlists:returnNonedefmergeTwoLists(l1,l2):dummyListNode()curdummywhilel1andl2:ifl1.vall2.val:cur.nextl1 l1l1.nextelse:cur.nextl2 l2l2.nextcurcur.nextifl1:cur.nextl1else:cur.nextl2returndummy.nextdefmerge(left,right):ifleftright:returnlists[left]mid(leftright)//2left_listmerge(left,mid)right_listmerge(mid1,right)returnmergeTwoLists(left_list,right_list)returnmerge(0,len(lists)-1)七、复杂度分析时间复杂度O(kn × logk)每一层需要遍历所有节点共有logk层。空间复杂度O(logk)主要来自递归调用栈。八、高频易错点1、返回值写错错误returndummy正确returndummy.next2、参数类型搞混merge()接收的是数组下标。mergeTwoLists()接收的是链表头节点。3、忘记接收递归返回值错误merge(left,mid)merge(mid1,right)正确left_listmerge(left,mid)right_listmerge(mid1,right)九、一句话总结合并 K 个链表的本质就是利用分治思想把问题不断拆成「合并两个有序链表」。