难以理解合并 K 排序列表的递归序列

Question

我一直在试图理解这个leetcode问题的递归顺序，我也找到了解决方案。我理解合并函数，但我不明白在合并KLists函数上发生的递归。帮助将不胜感激。请尽可能描述我显示导致最终合并链表的调用和返回。*我了解合并功能，因此无需解释。

def mergeKLists(self, lists):
if not lists:
return 
if len(lists) == 1:
return lists[0]
mid = len(lists)//2
l = self.mergeKLists(lists[:mid])
r = self.mergeKLists(lists[mid:])
return self.merge(l, r)
def merge(self, l, r):
dummy = cur = ListNode(0)
while l and r:
if l.val < r.val:
cur.next = l
l = l.next
else:
cur.next = r
r = r.next
cur = cur.next
cur.next = l or r
return dummy.next

Answer 1

mergeKLists成对合并列表，因此它们在合并时大小更相等，这意味着我们正在处理较小的子列表，因此我们避免了合并两个长度高度不均匀的列表的不均匀O(a+b(时间复杂度。递归模式类似于合并排序。

除非有经过分析证明的性能优势，并且现实世界需要额外的性能，否则我会在代码审查中拒绝这一点，并告诉作者改用 for 循环。我怀疑 for 循环在实践中可能会更快，即使他们使用的分而治之风格的递归在理论上更快。

如果性能真的很重要，并且我们有巨大的列表，那么编写一个直接合并 k 个列表的合并排序步骤会更快，方法是同步遍历所有 k 个列表并按顺序复制值，因为最后一个合并步骤的时间复杂度为 O(sum(map(length，k(((。当然，这将取决于首先在 O(n log n( 对每个列表进行排序的时间(如果我们使用基于比较的排序算法(。