ListNode的.next机制解析：为何tempFinalHead能保留前驱节点？

我的代码如下：

class Solution 
{
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) 
    {
        ListNode finalHead = new ListNode(0);
        ListNode tempFinalHead = finalHead;

        while(list1 != null && list2 != null)
        {
            if(list1.val < list2.val)
            {
                tempFinalHead.next = list1;
                list1 = list1.next; // 标记行1
            }
            else
            {
                tempFinalHead.next = list2;
                list2 = list2.next; // 标记行2
            }

            tempFinalHead = tempFinalHead.next; // 标记行3
        }

        if(list1 != null)
        {
            tempFinalHead.next = list1;
            list1 = list1.next;
        }

        if(list2 != null)
        {
            tempFinalHead.next = list2;
            list2 = list2.next;
        }

        return finalHead.next;
    }
}

我标记了三处使用.next更新ListNode的代码，现在有个核心疑问：执行tempFinalHead = tempFinalHead.next;时，之前保存的节点为什么不会丢失？比如输入list1 = [1,2,4]，list2 = [1,3,4]，输出是[1,1,2,3,4,4]，代码能正确运行，但我不理解每次用.next替换tempFinalHead时，它是如何维护所有前驱节点的。

另外我能理解list1 = list1.next;和list2 = list2.next;会让原链表指针后移（比如list1从1->2->4变成2->4），但搞不懂tempFinalHead相关的.next操作为什么能保留所有节点。

问题解答 #

核心原因是ListNode是引用类型，finalHead和tempFinalHead是指向链表节点的指针，而非节点本身，我们来拆解每一步的逻辑：

1. 初始状态：

   • 创建了一个哑节点finalHead（值为0），tempFinalHead和finalHead指向同一个节点。此时finalHead.next是null。

2. 关于标记行1和行2：

   • list1 = list1.next;和list2 = list2.next;只是移动原链表的遍历指针，把已经合并到新链表的节点跳过，去指向下一个待比较的节点。这一步不会修改已经合并到新链表中的节点，只是改变list1/list2变量的指向，对新链表没有影响。

3. 关于标记行3：

   • 当执行tempFinalHead.next = list1（或list2）时，我们是把当前选中的节点挂到新链表的尾部（tempFinalHead此时指向新链表的最后一个节点）。
   • 接着执行tempFinalHead = tempFinalHead.next;，只是把tempFinalHead这个指针移动到新链表的新尾部，而之前的节点并没有丢失——因为finalHead一直指向最开始的哑节点，它的.next链已经把所有合并的节点串起来了。

举个具体的步骤例子（对应输入list1=[1,2,4]，list2=[1,3,4]）：

• 第一步：比较1和1，取list1的1，tempFinalHead.next = list1（此时哑节点0的next变成1），list1移动到2->4，然后tempFinalHead移动到节点1。此时finalHead.next已经是1->2->4的开头，但后续会继续修改节点1的next。
• 第二步：比较list2的1和list1的2，取list2的1，tempFinalHead.next = list2（节点1的next变成1），list2移动到3->4，tempFinalHead移动到这个新的节点1。此时finalHead.next对应的链表是1->1->3->4。
• 后续步骤以此类推，每次都是把新节点挂到当前尾部的next，再把尾部指针后移，而finalHead始终牢牢握着整个链表的入口，所有前驱节点都通过.next链接在一起，不会丢失。

4. 最后拼接剩余节点：
   • 当其中一个链表遍历完后，把另一个链表的剩余部分直接挂到新链表的尾部即可，这一步也是通过tempFinalHead.next完成，同样不会破坏已经构建好的链表结构。

最后返回finalHead.next，就是跳过哑节点，得到合并后的完整有序链表。

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