Java中使用归并排序对链表排序失败问题排查

核心错误点 #

你的merge方法在处理左右链表剩余节点时逻辑错误：仅将剩余链表的第一个节点以新节点形式接入结果，丢弃了后续所有节点，导致排序后链表缺失部分元素。

修正后的完整代码 #

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode middle = findMiddle(head);
        ListNode rightHead = middle.next;
        middle.next = null;
        ListNode leftHead = head;
        leftHead = sortList(leftHead);
        rightHead = sortList(rightHead);

        return merge(leftHead,rightHead);
    }
    
    public ListNode merge(ListNode leftHead, ListNode rightHead){
        ListNode dummyHead = new ListNode(-1);
        ListNode temp = dummyHead;
        while(leftHead!=null && rightHead!=null){
            if(leftHead.val<rightHead.val){
                temp.next = leftHead;
                temp = leftHead;
                leftHead = leftHead.next;
            }else{
                temp.next = rightHead;
                temp = rightHead;
                rightHead = rightHead.next;
            }
        }
        // 直接拼接剩余的整个链表，无需逐个创建新节点
        if(leftHead!=null){
            temp.next = leftHead;
        }else if(rightHead!=null){
            temp.next = rightHead;
        }
        return dummyHead.next;
    }
    
    public ListNode findMiddle(ListNode head){
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

关键修正说明 #

1. 剩余节点处理逻辑：原代码中temp.next = new ListNode(leftHead.val)的写法仅保留了当前节点的值，切断了后续链表连接。修正后直接将temp.next指向剩余链表的头节点leftHead或rightHead，完整保留剩余的所有有序节点。
2. 移除冗余操作：删除了原代码中逐个移动temp的多余步骤，因为剩余链表本身已经是有序的，直接拼接即可。

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