148.排序链表

题目:148.排序链表

你链表的头结点 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^4] 内
-10^5 <= Node.val <= 10^5

• 进阶：

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

思路

将链表按升序排序可以通过 归并排序 来实现。归并排序非常适合链表，因为在链表中插入或拆分节点非常高效。归并排序的基本思路是：

1. 分割链表：使用快慢指针（快指针每次走两步，慢指针每次走一步），找到链表的中点，将链表分为两部分。
2. 递归排序：分别递归地对两部分进行排序。
3. 合并排序后的链表：最后将两个排序后的链表合并为一个排序好的链表。

• 时间复杂度:O(log₂n)
• 空间复杂度:O(log₂n)

代码

public ListNode sortList(ListNode head) {
    // 基础条件：如果链表为空或只有一个节点，直接返回
    if (head == null || head.next == null) {
        return head;
    }
    // 使用快慢指针找到链表的中间节点，拆分成两部分
    ListNode mid = findMid(head);
    ListNode left = head;
    ListNode right = mid.next;
    // 将链表从中间断开
    mid.next = null;
    // 递归地排序左半部分和右半部分
    left = sortList(left);
    right = sortList(right);
    // 合并两个排序好的链表
    return merge(left, right);
}

// 快慢指针找到链表的中间节点
private ListNode findMid(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

// 合并两个排序好的链表
private ListNode merge(ListNode left, ListNode right) {
    // 定义一个哑节点作为结果链表的起点
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    // 合并两个升序链表
    while (left != null && right != null) {
        if (left.val < right.val) {
            current.next = left;
            left = left.next;
        } else {
            current.next = right;
            right = right.next;
        }
        current = current.next;
    }
    // 如果左链表还有剩余，接上
    if (left != null) {
        current.next = left;
    }
    // 如果右链表还有剩余，接上
    if (right != null) {
        current.next = right;
    }
    // 返回合并后的链表（跳过哑节点）
    return dummy.next;
}