合并有序链表代码为何引发无限循环？

我在完成LeetCode的有序链表合并题目时，错误地将list1 = list1.next/list2 = list2.next放在result.next = list1/result.next = list2之前，导致程序出现无限循环。调试后仍无法理解问题成因，特寻求解释。

输入的两个有序链表为：

• list1: 1 → 2 → 4
• list2: 1 → 3 → 4

错误代码 #

// Loop until list1 and list2 is not empty
while (list1 != null && list2 != null) {
    if (list1.val < list2.val) {
        list1 = list1.next;
        result.next = list1;
        
    } else {
        list2 = list2.next;
        result.next = list2;
        
    }

    System.out.println(list2.val);

    result = result.next;
}

正确代码 #

while (list1 != null && list2 != null) {
    if (list1.val < list2.val) {
        
        result.next = list1;
        list1 = list1.next;
        
    } else {
        
        result.next = list2;
        list2 = list2.next;
        
    }

    System.out.println(list2.val);

    result = result.next;
}

调试观察到的现象 #

调试过程中发现result链表的值会不断循环：4,2,3 → 2,4,2 → 4,2,3 → 2,4,2……交替出现，关键迭代状态如下：

• 倒数第二次迭代：result指向节点4，list1为null，list2指向节点2
• 最后一次迭代：result指向节点2，list1为null，list2指向节点4

问题成因解析 #

核心问题是顺序颠倒导致链表引用形成循环，同时原链表指针无法终止循环条件，具体拆解：

1. 错误逻辑的执行流程 #

以list1.val < list2.val的分支为例，错误代码先执行list1 = list1.next，将list1指针移动到下一个节点，再把这个移动后的节点挂载到result.next。这会导致两个问题：

• 跳过了list1原本的当前节点，结果链表缺失元素；
• 当移动后的list1/list2节点已经存在于result链中时，挂载操作会让result链表形成循环引用。

2. 无限循环的触发点 #

当result链表形成循环后，原链表的list1/list2指针会指向循环中的节点，这些节点的next永远不会为null，导致while(list1 != null && list2 != null)的循环条件永远成立，程序陷入无限循环。

比如在你的调试场景中，result链出现了4→2→4的循环：当result指向节点4时，result.next被设置为节点2；当result移动到节点2时，result.next又被设置为节点4，如此反复，同时list1/list2始终指向循环中的非null节点，循环永远无法终止。

3. 正确逻辑的合理性 #

正确代码先将当前list1/list2节点挂载到result.next，再移动原链表指针。这样既不会跳过节点，也不会让result链引用已存在的节点（原链表指针移动后指向的是未被处理的新节点），原链表指针会逐步走到null，循环正常终止。

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