题目

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目在范围 [0, 5 * 10⁴] 内
• -10⁵ <= Node.val <= 10⁵

进阶： 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

题解

public ListNode sortList(ListNode head) {
    // 当链表只有一个节点时 就是有序的
    if (head == null || head.next == null) {
        return head;
    }

    // 归并排序
    // 快慢指针遍历出中间节点
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 将链表分割成两部分
    ListNode right = this.sortList(slow.next);
    slow.next = null;
    ListNode left = this.sortList(head);

    ListNode node = new ListNode(0);
    ListNode cursor = node;
    // 合并两个链表
    while (left != null && right != null) {
        if (left.val < right.val) {
            cursor.next = left;
            left = left.next;
        } else {
            cursor.next = right;
            right = right.next;
        }
        cursor = cursor.next;
    }

    cursor.next = left != null ? left : right;

    return node.next;
}