leetcode hot100

148. 排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

思路一：递归 + 归并

思路参考：https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/

使用递归归并排序

快慢指针找到链表中点后分割链表为左右两段，递归分割左右链表，然后合并两个链表，返回合并后的结果

 1 class Solution {
 2     public ListNode sortList(ListNode head) {
 3 
 4         // 使用递归归并排序
 5         if(head == null || head.next == null){
 6             return head;
 7         }
 8 
 9         // 快慢指针找到链表中点后分割链表为左右两段
10         ListNode slow = head, fast = head.next;
11         while(fast != null && fast.next != null){
12             slow = slow.next;
13             fast = fast.next.next;
14         }
15         ListNode tmp = slow.next;   // 第二段链表，前面的作为第一段链表
16         slow.next = null;           // 第一段链表和第二段链表断开连接
17 
18         // 递归分割左右链表
19         ListNode left = sortList(head);
20         ListNode right = sortList(tmp);
21 
22         ListNode res = new ListNode();  // 定义一个空节点，简化合并操作
23         ListNode cur = res;             // 
24         // 合并两个链表
25         while(left != null && right != null){
26             if(left.val < right.val){
27                 cur.next = left;
28                 left = left.next;
29             }else{
30                 cur.next = right;
31                 right = right.next;
32             }
33             cur = cur.next;
34         }
35         cur.next = left == null ? right : left;
36         return res.next;
37     }
38 }

leetcode 执行用时：3 ms > 98.99%, 内存消耗：40.9 MB > 66.19%

复杂度分析：

时间复杂度：归并排序的时间复杂度为O(nlogn), 虽然多了一个遍历链表找中点的操作，但是对于同一层的链表，复杂度为O(n), 递归深度为O(logn), 所以时间复杂度为O(nlogn)

空间复杂度：没有借助额外的容器，但是递归本身需要一个递归栈，栈的深度为O(nlogn), 所以空间复杂度为O(nlogn)

思路二：迭代 + 归并

思路参考：https://leetcode-cn.com/problems/sort-list/comments/

虽然上面解法通过了测试，但是其实是不符合题意的，因为题目要求空间复杂度为O(1), 但是我们使用递归后空间复杂度明显不是O(1),所以需要把递归方式改成迭代方式。

 1 class Solution {
 2     public ListNode sortList(ListNode head) {
 3         // 非递归归并排序
 4         
 5         // 先统计链表长度
 6         ListNode tmp = new ListNode();
 7         tmp.next = head;
 8         ListNode p = head;
 9         int length = 0;
10         while(p != null){
11             p = p.next;
12             length++;
13         }
14 
15         // 主循环，控制每次归并的链表的大小，从1-n/2,成倍扩大
16         for(int size = 1; size < length; size <<= 1){
17             ListNode cur = tmp.next;
18             ListNode tail = tmp;    // 简化连接
19 
20             while(cur != null){
21                 // 从链表中取下固定大小的结点，取两段
22                 ListNode left = cur;
23                 ListNode right = cut(left, size);
24                 cur = cut(right, size);             // 更新cur指针的位置
25                 // 归并这两段
26 
27                 tail.next = mergeList(left, right);
28 
29                 // 把归并后的结果挂到有序链表尾部
30                 while(tail.next != null){
31                     tail = tail.next;
32                 }
33             }
34         }
35         return tmp.next;
36     }
37 
38     // 从链表中取下固定大小的结点
39     public ListNode cut(ListNode head, int n){
40         ListNode p = head;
41         // 先跳过n个结点
42         while(--n != 0 && p != null){
43             p = p.next;
44         }
45         if(p == null){
46             return p;
47         }
48         ListNode next = p.next;
49         // 返回跳过size个结点的指针
50         p.next = null;
51         return next;
52     }
53 
54     // 合并两个链表
55     public ListNode mergeList(ListNode left, ListNode right){
56         ListNode res = new ListNode();
57         ListNode cur = res;
58         while(left != null && right != null){
59             if(left.val < right.val){
60                 cur.next = left;
61                 left = left.next;
62             }else{
63                 cur.next = right;
64                 right = right.next;
65             }
66             cur = cur.next;
67         }
68         cur.next = (left != null ? left : right);
69         return res.next;
70     }
71 }

希望同学们能把双路归并和 cut 断链的代码烂记于心，以后看到类似的题目能够刷到手软。

leetcode执行用时：7 ms > 27.29%, 内存消耗：40.9 MB > 63.86%

复杂度分析：

时间复杂度：这个就是标准的归并排序，所以时间复杂度为O(nlogn)

空间复杂度：没有借用集合，有没有借用递归，所以复杂度为O(1)