LeetCode 21题合并有序链表：递归深度溢出问题求助

测试用例：list1=[1,2,4]、list2=[1,3,4]，期望输出[1,1,2,3,4,4]，但代码第22行触发了Python的最大递归深度错误。你疑惑代码按从上到下、从左到右执行的逻辑，不该出现无限递归，问题出在哪？

你的代码：

class Solution(object):
def mergeTwoLists(self, list1, list2):
    if not list1 and not list2:
        return list1
    if not list1 and list2:
        return list2
    if not list2 and list1:
        return list1
    New_Node = ListNode(0)
    temp = New_Node
    
    def Traversal(list1, list2, temp):
        if not list1:
            temp.next = list2
            return
        if not list2:
            temp.next = list1
            return

        if list1.val >= list2.val:
            temp.next = list2
            Traversal(list1, list2.next, temp.next)
        if list2.val >= list1.val:
            temp.next = list1
            Traversal(list1.next, list2, temp.next)
    
    Traversal(list1, list2, temp)
    return New_Node.next

问题原因 #

核心问题是两个if条件没有互斥：当list1.val等于list2.val时（比如测试用例里两个链表的第一个节点值都是1），list1.val >= list2.val和list2.val >= list1.val这两个条件会同时成立。

执行流程会变成这样：

1. 第一个if执行：把temp.next设为list2的节点，触发递归调用Traversal(list1, list2.next, temp.next)
2. 递归返回后，代码继续走第二个if：此时条件依然满足，又把temp.next改成list1的节点，再次触发递归调用Traversal(list1.next, list2, temp.next)
3. 同一个节点位置被反复修改，递归调用不断触发，直接陷入无限循环，最终触发递归深度溢出错误。

修复方案 #

把第二个if改成elif，让两个条件互斥，只会执行其中一个：

if list1.val >= list2.val:
    temp.next = list2
    Traversal(list1, list2.next, temp.next)
elif list2.val >= list1.val:  # 改用elif
    temp.next = list1
    Traversal(list1.next, list2, temp.next)

或者更简洁，直接用else（因为两个链表是有序的，只要第一个条件不满足，必然是list2.val > list1.val）：

if list1.val >= list2.val:
    temp.next = list2
    Traversal(list1, list2.next, temp.next)
else:
    temp.next = list1
    Traversal(list1.next, list2, temp.next)

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