递归实现合并K个排序链表时触发最大递归深度错误的问题排查

你遇到的这个递归深度超限问题，根源在于代码没有处理链表数组为空的边界场景，导致了无限递归调用。咱们一步步拆解问题：

问题分析 #

你的递归终止条件只覆盖了len(lists) == 1和len(lists) == 2的情况，但完全没考虑当输入是[]（空数组）时的处理逻辑。当测试用例是[]时，代码会直接执行下面的递归拆分：

v1 = self.mergeKLists(lists[:len(lists)//2])  # len(lists)为0，拆分后还是空数组
v2 = self.mergeKLists(lists[len(lists)//2:])  # 同样是空数组

这会导致函数无限调用mergeKLists([])，直到触发Python的最大递归深度限制，抛出RecursionError。

另外还有个潜在小问题：如果输入数组里包含空链表（比如测试用例[[]]），虽然当前代码能返回空链表，但如果拆分过程中出现[None, None]这类情况，虽然不会导致递归错误，但会增加不必要的递归开销。

修复方案 #

我们需要在递归的最开头先处理这些边界场景，同时优化合并两个链表的逻辑提升性能：

1. 先过滤空链表：把数组中所有None（空链表）都过滤掉，避免无效的递归调用
2. 处理空数组场景：过滤后如果数组为空，直接返回None
3. 优化合并逻辑：合并两个链表时，不用逐个创建新节点，直接拼接剩余的链表即可，提升效率

修改后的完整代码如下：

# 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]:
        # 先过滤掉所有空链表，减少无效递归
        lists = [l for l in lists if l is not None]
        # 处理空数组的情况
        if not lists:
            return None
        if len(lists) == 1:
            return lists[0]
        elif len(lists) == 2:
            return self.merge2Lists(lists[0], lists[1])

        mid = len(lists) // 2
        v1 = self.mergeKLists(lists[:mid])
        v2 = self.mergeKLists(lists[mid:])

        return self.merge2Lists(v1, v2)
    
    def merge2Lists(self, list1, list2):
        result = ListNode()
        cur = result
        
        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
        
        # 直接拼接剩余的链表，无需逐个创建新节点
        if list1:
            cur.next = list1
        if list2:
            cur.next = list2
        
        return result.next

修复效果 #

• 测试用例[]会直接返回None，不会触发无限递归
• 测试用例[[]]过滤后变成空数组，也会正确返回None
• 正常的多链表测试用例能按分治逻辑正确递归拆分合并，同时合并过程的性能也得到了优化

备注：内容来源于stack exchange，提问作者Aarav Shah