原地合并两个有序链表时出现无限循环的原因排查

你好！从你的思路描述和代码来看，你尝试用递归+全局变量的方式实现原地合并，但遇到了无限循环和逻辑错误，我来帮你拆解问题所在，同时给出修正方向：

一、核心问题分析（导致无限循环/错误的原因） #

1. 全局变量t的误用 #

你用全局变量t标记首次调用、维护前驱节点head的引用，但这完全不适合递归场景：

• 递归调用时，每个函数栈的head是独立的局部变量，无法在递归层级间共享前驱节点的状态；
• 全局变量t在函数被多次调用（比如测试多个用例）时不会自动重置，会导致后续调用逻辑完全混乱；
• 非首次递归调用时，head变量可能未被赋值就被使用（比如进入head1.data >= head2.data分支），直接触发NameError。

2. 分支顺序逻辑错误 #

你的代码先比较节点data，再判断空节点，这会直接引发报错：
当head1或head2为None时，访问head1.data会抛出AttributeError（None没有data属性），且空节点的判断分支被放在后面，根本不会被执行到。

3. 空节点处理的语法错误 #

代码中head2!=none使用了小写的none，但Python中正确的空值是大写的None，这会触发NameError: name 'none' is not defined，导致后续逻辑完全无法执行。

4. 递归参数传递错误 #

在处理head2节点插入list1的逻辑后，你递归调用mergeSortedList(head1, head2)，但此时head1没有移动，head2却跳到了下一个节点。这种参数传递会导致重复处理同一个head1节点，进而引发无限递归（无限循环）。

二、修正思路与正确实现 #

原地合并有序链表的核心是维护前驱节点指针，用迭代方式更清晰可靠（递归反而容易引发栈溢出或状态混乱）。以下是修正后的原地合并实现：

# 假设链表节点的定义为：
class ListNode:
    def __init__(self, data=0, next=None):
        self.data = data
        self.next = next

def merge_sorted_lists(head1, head2):
    # 处理其中一个链表为空的边界情况
    if not head1:
        return head2
    if not head2:
        return head1
    
    # 用哑节点统一处理头节点不确定的情况
    dummy = ListNode(-1)
    current = dummy
    
    # 迭代合并两个有序链表
    while head1 and head2:
        if head1.data <= head2.data:
            current.next = head1
            head1 = head1.next
        else:
            current.next = head2
            head2 = head2.next
        current = current.next
    
    # 挂载剩余未处理完的节点
    current.next = head1 if head1 else head2
    
    return dummy.next

如果一定要用递归实现，正确的方式是通过参数传递剩余节点，而非全局变量，示例如下：

def merge_sorted_lists_recursive(head1, head2):
    # 递归终止条件：其中一个链表为空
    if not head1:
        return head2
    if not head2:
        return head1
    
    # 选择较小的节点作为当前节点，递归处理剩余部分
    if head1.data <= head2.data:
        head1.next = merge_sorted_lists_recursive(head1.next, head2)
        return head1
    else:
        head2.next = merge_sorted_lists_recursive(head1, head2.next)
        return head2

三、针对你原思路的具体修正建议 #

如果你坚持要沿用自己的原地插入思路，需要做以下调整：

1. 移除全局变量：将前驱节点作为递归参数传递，而非用全局变量跟踪；
2. 调整分支顺序：先判断空节点，再比较data属性；
3. 修正语法错误：把所有小写的none改为Python标准的None；
4. 修正递归参数：插入head2节点后，应递归处理head1和head2的剩余部分，而非原head1节点。

备注：内容来源于stack exchange，提问作者Abhiram Vartak