有序单链表递归归并时间复杂度分析及递归迭代对比

时间复杂度结论 #

你对时间复杂度的判断方向基本正确，准确的时间复杂度为 O(m + n)，其中m、n分别为两个输入链表的长度，递归调用本身不会额外提升时间复杂度。

你贴出的实现代码如下：

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if(list1 is None and list2 is not None):
            return list2;
        elif(list1 is not None and list2 is None):
            return list1;
        elif(list1 is not None and list2 is not None):
            if(list1.val > list2.val):
                return ListNode(list2.val, self.mergeTwoLists(list1, list2.next));
            elif(list2.val >= list1.val):
                return ListNode(list1.val, self.mergeTwoLists(list1.next, list2));
        else:
            return None

这个实现里，每进入一次递归调用，只会完成两个节点值的比较、选择更小值创建新节点，然后把其中一个链表的指针向后移动一位传入下一层递归，不存在重复访问节点的情况。直到其中一个链表遍历完成，直接拼接另一个链表的剩余部分，总递归调用次数恰好等于两个链表的节点总数，单次调用内的操作都是常数时间O(1)，因此总时间开销和迭代实现完全一致。

注意不要把递归的空间开销和时间开销混淆：这个实现的递归栈深度等于总节点数，加上每次新建节点的开销，空间复杂度是O(m + n)，但这部分属于空间成本，不影响时间复杂度计算。

线性递归函数时间复杂度分析技巧 #

针对这类单链递归（每次调用最多产生1次下一层递归，无多分支递归调用）的场景，可以按三个步骤快速计算复杂度：

• 先剥离递归调用部分，计算单次函数调用内固定操作的时间成本，这类链表操作的单步逻辑基本都是O(1)常数时间。
• 统计递归总调用次数：沿着递归调用的推进逻辑，数清楚从初始调用到触发终止条件，总共会产生多少次调用。对于合并链表的场景，每次调用一定会让其中一个链表的待处理长度减1，总次数就是两个链表长度之和。
• 排除递归栈的空间成本影响：递归栈占用的内存属于空间复杂度范畴，不会增加执行的操作总次数，不需要计入时间复杂度。

如果是存在多次递归调用的分叉场景（比如斐波那契递归、二叉树遍历），再通过画递归调用树统计所有节点的总操作数即可。

该场景下递归实现相比迭代实现的优势 #

• 代码逻辑和问题的数学定义完全对齐：合并两个有序链表的递归定义本身就是「取两个链表头节点的较小值，拼接在剩余两个链表合并结果的头部」，递归写法是这个定义的直接翻译，不需要手动维护遍历指针、前驱节点等临时变量，写的时候不容易出现指针偏移、边界判断遗漏的bug。
• 边界处理更自然：两个链表任意一个为空的终止场景，直接作为递归出口处理，不需要在迭代循环里额外嵌套分支判断空值，代码结构更简洁可读性更高。
• 代码量更短，逻辑分层清晰，后续维护时更容易快速理解实现意图。

内容的提问来源于stack exchange，提问作者Jokester2