这里的空间复杂度O（m + n）如何？

Question

合并两个排序的链表，并将其作为新列表返回。应该通过将前两个列表的节点拼接在一起来创建新列表。

class Solution:
    def mergeTwoLists(self, l1, l2):
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

我知道它与堆栈有关。有人可以为我说清楚吗？我对此表示陌生。

Answer 1

该算法的基本原理是，每个递归调用都从l1或l2中选择一个元素。由于只能发生M + N次，因此时间复杂度将为O(M + N)。

空间复杂性是另一回事。

我知道它与堆栈有关。

是。在Python中，递归调用的每个递归级别都需要一个堆栈框架。堆栈框架包含调用参数和局部变量，以及允许调用返回到调用它的代码中正确位置所需的信息。

在您的示例中，有M + N个级别，因此堆栈空间的空间复杂度为O(M + N)。

假设您以明显的方式实现了链表节点，那么您的合并方法将使l1和l2对象发生变异，并且不再占用更多空间。

---

许多语言/编译器在某些情况下支持递归调用自身的方法在许多情况下都支持尾调用优化

。尽可能将递归调用优化为跳转到方法的开始，而不是使用调用指令。因此，不需要堆栈框架。

在您的示例中，堆栈使用的空间复杂度将是

O(1)。

但是Python 不

支持此；参见Does Python optimize tail recursion?