链表中等1 种解法

#148排序链表

使用适合链表的归并排序，在 O(n log n) 时间内按升序排列节点。

#链表#归并排序#双指针

解题主线

fast 从 head.next 出发，使偶数长度时 slow 停在前半段尾节点，确保能正确断链。

链表合并只修改 next，不需要数组搬移元素。

解法 1：自顶向下归并排序

快慢指针二分链表，分别递归排序左右半段，再线性合并。

时间复杂度

O(n log n)

空间复杂度

O(log n)（递归栈）

148. 排序链表 · 自顶向下归并排序

java

public class Solution {
    static final class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode rightHead = slow.next;
        slow.next = null;

        return merge(sortList(head), sortList(rightHead));
    }

    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                tail.next = left;
                left = left.next;
            } else {
                tail.next = right;
                right = right.next;
            }
            tail = tail.next;
        }
        tail.next = left != null ? left : right;
        return dummy.next;
    }
}

快慢指针二分链表，分别递归排序左右半段，再线性合并。

边界与易错点

若 fast 与 slow 都从 head 出发且直接在 slow 后断链，两节点输入可能无法缩小递归规模。
自顶向下归并会占用 O(log n) 递归栈，不能标为严格 O(1) 额外空间。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

Q148_linkedList_sort_list.java