1. 题目

2. 读题（需要重点注意的东西）

思路（迭代的归并排序）：

要求： 时间复杂度为O(nlog(n)） 空间复杂度为O(1)

各种排序算法的时间复杂度与空间复杂度：

排序算法	平均时间复杂度	空间复杂度
快速排序	O(nlogn)	O(logn)
归并排序	O(nlogn)	递归 O(logn) 迭代 O(1)
堆排序	O(nlogn)	O(1)

但是链表不能用堆排序，因此根据要求，选择使用迭代的归并排序。
迭代法： 设 n为链表总长度，首先将链表划分为长度为1的区间，再两两排序后合并，再迭代执行两两合并，直到链表长度为n即可。

• dummy.next始终指向链表的开头；
• p指向合并的区间1的起始节点，q指向区间2的起始节点，用cur存储合并后的链表；
• o指向下一段合并的区间1的起始节点，head指向o，准备在下一次合并赋给p，重复上述合并过程。
  

3. 解法

---------------------------------------------------解法---------------------------------------------------：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        // 求链表长度
        int n = 0;
        for(ListNode p = head;p != null;p = p.next) n ++;

        // i表示每层合并的区间长度
        // 每层两两合并 1 -> 2 -> 4 -> ... -> n
        // 当i == n的时，代表合并结束了，退出循环
        // 每次合并后 i*2 ，翻倍
        for(int i = 1;i < n;i *= 2){
            // 由于排序，每层的头结点会改变，在每一层都定义一个虚拟头结点 dummy
            // 用cur来存储合并后的链表
            ListNode dummy = new ListNode(-1), cur = dummy;
            // j 为区间的开头，对 每两段 区间进行排序、合并（两两合并）
            // i 为每一段的长度，因此 j + i 表示下一段的开头， j + i * 2 表示j向后走两段
            for(int j = 1;j <= n;j += i * 2){
                // 开始考虑具体的两两合并，【区间1】【区间2】 两两合并
                // p指针指向第一个区间的起始节点
                ListNode p = head, q = p;
                // q指针指向下一个区间的起始节点，即 q 在 p 的位置上向后走 i 步
                for(int k = 0;k < i && q != null;k ++) q = q.next;
                
                // o存储下一次合并的第一个区间的起始节点
                ListNode o = q;
                for(int k = 0;k < i && o != null;k ++) o = o.next;

                // 已经有了两段链表的起始节点 p 和 q ，开始具体的归并排序
                // ---------- 归并排序开始 -----------
                int l = 0,r = 0;
                while(l < i && r < i && p != null && q != null){
                    if(p.val <= q.val) {
                        cur.next = p;
                        p = p.next;
                        l ++;
                    }else{
                        cur.next = q;
                        q = q.next;
                        r ++;
                    }
                    cur = cur.next;
                }
                // 如果链表q空了，p不为空，将链表p接到cur后
                while(l < i && p != null) {cur = cur.next = p; p = p.next; l ++;}
                // 如果q不为空
                while(r < i && q != null) {cur = cur.next = q; q = q.next; r ++;}
                // ---------- 归并排序结束 -----------
                // head指向下一次合并的第一个区间的起始节点
                head = o;
            }
            // 合并完一层
            // 如果不将cur置为null，会产生环
            cur.next = null;
            // 更新head为起始节点，准备赋值给p
            head = dummy.next;
        }

        return head;
    }
}

---

可能存在的问题：

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

• 归并排序

6. 总结