大家好！我是曾续缘😹

今天是《LeetCode 热题 100》系列

发车第 33 天

链表第 12 题

❤️点赞 👍 收藏 ⭐再看，养成习惯

排序链表

给你链表的头结点 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 * 104] 内
• -105 <= Node.val <= 105

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

难度：💖💖

解题方法

这道题目是要求对链表进行排序，要求使用 O(nlogn) 的时间复杂度和常数级的空间复杂度。给定的是单向链表的头结点 head，需要返回排序后的链表。

我们使用经典的归并排序来解决这个问题，需要说明的是，下面的是递归版本，并不符合常数级的空间复杂度。归并排序的基本思想是将链表分成两部分，然后分别对这两部分进行排序，最后再合并这两部分成一个有序的链表。

步骤如下：

1. 首先，在 sortList 方法中，先判断特殊情况，即如果链表为空或者只有一个节点，则直接返回该链表，因为它已经是有序的。
2. 然后，通过快慢指针的方法找到链表的中间节点（slow 指针），将链表一分为二，分别用 lbegin 和 rbegin 表示左右两部分的链表头。
3. 接下来，递归地对左右两部分链表调用 sortList 方法，直到无法再分割（即链表为空或者只有一个节点）。这样就实现了将原始链表分成了若干个小的有序链表。
4. 最后，将左右两部分的有序链表通过 mergeTwoLists 方法进行合并，得到最终的有序链表，mergeTwoLists 方法在 LeetCode 的 21. 合并两个有序链表 中有实现过。

Code

/**
 * 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 fast = head.next, slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode rhead = slow.next;
        slow.next = null;
        ListNode lbegin = sortList(head);
        ListNode rbegin = sortList(rhead);
        return mergeTwoLists(lbegin, rbegin);
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 21.合并两个有序链表
        if(list1 == null){
            return list2;
        }else if(list2 == null){
            return list1;
        }else if(list1.val < list2.val){
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}