排序链表 - LeetCode 热题 33

大家好！我是曾续缘😹

今天是《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 * 10⁴] 内
-10⁵ <= Node.val <= 10⁵

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

解题方法

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

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

步骤如下：

首先，在 sortList 方法中，先判断特殊情况，即如果链表为空或者只有一个节点，则直接返回该链表，因为它已经是有序的。
然后，通过快慢指针的方法找到链表的中间节点（slow 指针），将链表一分为二，分别用 lbegin 和 rbegin 表示左右两部分的链表头。
接下来，递归地对左右两部分链表调用 sortList 方法，直到无法再分割（即链表为空或者只有一个节点）。这样就实现了将原始链表分成了若干个小的有序链表。
最后，将左右两部分的有序链表通过 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;}}
}