Java合并有序链表：root.next与prev.next为何是合并链表头？

给定两个有序链表的头节点list1和list2，以下是两种Java实现方案，针对代码中的两个疑问做清晰解释：

方案一（Solution） #

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        final ListNode root = new ListNode();
        ListNode prev = root;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                prev.next = list1;
                list1 = list1.next;
            } else {
                prev.next = list2;
                list2 = list2.next;
            }
            prev = prev.next;
        }
        prev.next = list1 != null ? list1 : list2;
        return root.next;
    }
}

方案二（SolutionTwo） #

class SolutionTwo {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode root = new ListNode();
        ListNode prev = root;

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

        root.next = list1 != null ? list1 : list2;
        
        return prev.next;  // Return the head of the merged list
    }
}

疑问1：为什么Solution中root.next是合并后链表的头节点？ #

这里的root是一个哨兵节点（dummy node），核心逻辑：

• 初始化时，prev和root指向同一个节点对象
• 第一次进入循环时，执行prev.next = list1或prev.next = list2，这本质就是给root.next赋值（此时prev和root是同一个引用），这个被赋值的节点就是合并后链表的第一个有效节点
• 之后prev = prev.next让prev往后移动，但root始终停留在初始的哨兵节点位置，它的next不会再被修改，因此最终root.next就是合并链表的头节点

疑问2：为什么SolutionTwo中prev.next能返回合并后链表的头节点？ #

核心是prev的引用从未改变：

• 初始时，prev和root指向同一个哨兵节点
• 循环中root不断往后移动（root = root.next），但prev始终停留在初始的哨兵节点
• 第一次循环时，root.next被赋值为合并链表的第一个有效节点，此时prev.next和root.next是同一个值（因为初始时prev和root是同一个节点）
• 后续root移动时，只会修改自身的next，不会影响prev的next，因此最终prev.next就是合并链表的头节点

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