leetcode 148. Sort List | 148. 排序链表（最优解归并排序，O(1)空间）

布满荆棘的人生 2022-09-05 12:58 191阅读 0赞

## 题目 ##

[https://leetcode.com/problems/sort-list/][https_leetcode.com_problems_sort-list]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

#### 分析 ####

就链表排序问题来说，它的解法可以有好多种。但它的最优解应该只有一种思路，即从下至上的归并，时间复杂度 O(nlogn)，空间复杂度 O(1)。详见本文的实现。

另外，还有一些其他的方法，例如：

*  时间复杂度O(n^2)的 **冒泡**，**插入**
 *  空间复杂度O(n)的 **任意额外空间排序**，最后再把链表重新串起来
 *  时间复杂度O(nlogn)，空间复杂度O(logn)的 **快排**
 *  时间复杂度O(nlogn)，空间复杂度O(logn)的从上至下 **归并**
 *  …

最优解（归并）比较绕，我的办法是多用几个变量把中间状态接住，两层 while 循环，外层控制 step，内层控制每一小组内的归并排序，需要注意的是，内层循环中，当前小组的前后组都不要断掉，所以需要记录 preTail 和 nextHead，分别表示前一组的终点和后一组的起点，方便前后的衔接。

关于本算法的时间复杂度计算，可以使用 Master 公式：

#### Master公式 ####

##### 简介 #####

在编程中，递归是非常常见的一种算法，但递归相比顺序执行或循环程序，时间复杂度难以计算，而master 公式就是用来计算递归程序的时间复杂度。

##### 公式 #####

`T(N) = aT(N/b) + O(N^d)`

*  b：子过程的样本量
 *  a：子过程的计算次数
 *  O(N^d)：子结果合并的时间复杂度

满足如上公式的程序，都可以根据master公式计算时间复杂度：

*  log(b，a) > d ：时间复杂度为O(N^log(b，a))
 *  log(b，a) = d ：时间复杂度为O(N^d \* logN)
 *  log(b，a) < d ：时间复杂度为O(N^d)

#### 附草稿 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

#### 代码 ####

/** * 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) { 
            int len = 0;
            ListNode t = head;
            while (t != null) { 
                t = t.next;
                len++;
            }
    
            int step = 1;
            ListNode p1;
            ListNode p2;
            ListNode preTail;
            ListNode nextHead;
            ListNode newHead = new ListNode();
            newHead.next = head;
            
            while (step <= len) { 
                p1 = newHead.next;
                preTail = newHead;
                while (p1 != null) { 
                    // - - - 初始化各种位置 - - -
                    // 找好p1,p2位置 注意超出边界的情况
                    p2 = p1;
                    for (int i = 0; i < step; i++) { 
                        if (p2 != null) p2 = p2.next;
                    }
                    if (p2 == null) break;
                    nextHead = p2;
                    for (int i = 0; i < step; i++) { 
                        if (nextHead != null) nextHead = nextHead.next;
                    }
                    // - - - 每组排序 - - -
                    // 如果p2=null,说明这组已经有序
                    ListNode tp1 = p1;
                    ListNode tp2 = p2;
                    // 和上一段接上
                    ListNode sortedTail = preTail;
                    if (tp1.val < tp2.val) { 
                        preTail.next = tp1;
                        tp1 = tp1.next;
                    } else { 
                        preTail.next = tp2;
                        tp2 = tp2.next;
                    }
                    sortedTail = sortedTail.next;
                    while (tp1 != p2 && tp2 != nextHead) {  // 归并排序
                        if (tp1.val < tp2.val) { 
                            sortedTail.next = tp1;
                            tp1 = tp1.next;
                        } else { 
                            sortedTail.next = tp2;
                            tp2 = tp2.next;
                        }
                        sortedTail = sortedTail.next;
                    }
                    while (tp1 != p2) {  // 处理剩余部分
                        sortedTail.next = tp1;
                        tp1 = tp1.next;
                        sortedTail = sortedTail.next;
                    }
                    while (tp2 != nextHead) {  // 处理剩余部分
                        sortedTail.next = tp2;
                        tp2 = tp2.next;
                        sortedTail = sortedTail.next;
                    }
                    // - - - 排序后的处理 - - -
                    sortedTail.next = nextHead; // 和下一段接上，如果到终点，则nextHead=null，避免了成环
                    for (int i = 0; i < step * 2; i++) {  // 更新preTail
                        if (preTail != null) preTail = preTail.next;
                    }
                    p1 = nextHead;
                }
                step *= 2;
            }
            return newHead.next;
        }
    }

一把过  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_sort-list]: https://leetcode.com/problems/sort-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/d711a7a52285456cadd4bde34275aa73.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/c6e384fa6e554d1b98ce4a790600e7eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/2dae579a16844f2d9a4867a6523f7718.png