23. 合并 K 个升序链表

题目链接：23. 合并 K 个升序链表

题目描述

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

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

核心思考：分治法（归并思想）

合并 $K$ 个有序链表有多种策略，如逐一合并或使用最小堆。本代码采用了基于**分治（Divide and Conquer）**的归并思想，类似于归并排序。

1. 分而治之：将 $K$ 个链表的数组不断二分为更小的子集。
   • 当数组长度为 0 或 1 时，直接返回结果作为基础解。
   • 分别递归处理左半部分和右半部分的链表，获取合并后的两个子链表。
2. 两两合并：编写辅助函数 merge_two，负责将两个已经有序的链表合并成一个。
   • 使用 dummy 节点和双指针技巧，按大小顺序依次链接。
3. 优势：
   相比于逐一合并（第一个与第二个合并，结果再与第三个合并…），分治的思想能够将合并的总层数控制在 $\log K$。这样每个节点被参与合并操作的次数更均匀，能有效提升整体性能。

解题思路 (Python)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        l = len(lists)
        # 递归边界
        if l == 0:
            return None
        if l == 1:
            return lists[0]
        
        # 二分并递归合并
        left = self.mergeKLists(lists[:l // 2])
        right = self.mergeKLists(lists[l // 2:])
        return self.merge_two(left, right)

    def merge_two(self, list1, list2):
        # 合并两个有序链表的标准实现
        cur = dummy = ListNode()
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        
        # 链接剩余部分
        cur.next = list1 if list1 else list2
        return dummy.next

复杂度分析

• 时间复杂度：$O(N \log K)$，其中 $N$ 是所有链表中的节点总数，$K$ 是链表的数量。分治过程共有 $\log K$ 层，每一层涉及到的合并工作量总和为 $N$。
• 空间复杂度：$O(\log K)$。主要开销为分治过程中的递归调用栈深度。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

num1 num2 num3 ... numN

输入一行整数数组，以空格分隔。

完整代码：

import sys

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    l = len(lists)
            # 递归边界
            if l == 0:
                return None
            if l == 1:
                return lists[0]

            # 二分并递归合并
            left = self.mergeKLists(lists[:l // 2])
            right = self.mergeKLists(lists[l // 2:])
            return self.merge_two(left, right)

def main():
    nums = list(map(int, sys.stdin.read().strip().split()))

    sol = Solution()
    result = sol.mergeKLists(nums)
    for v in result:\n        print(v, end=' ')\n    print()

if __name__ == "__main__":
    main()

运行示例：

echo "2 -1 3 4 -5" | python solution.py