本题对链表进行升序排列，要求排序的时间复杂度为 O(nlogn) 以及 空间复杂度为 O(1)。回顾十大排序算法，时间复杂度为 O(nlogn) 的算法有堆排序、快速排序、归并排序（快排的时间复杂度最坏为 O(n²)）。

这道题求解选择归并排序。

问：对链表进行排序，为什么用堆排序，不能用快速排序？

答：快排的核心思想是左右指针做到元素的交换并找到分割点实现分区，而数组可以通过下标 O(1) 的时间复杂度随机访问任意元素正好满足快排高速的需求。但是访问链表的节点只能通过遍历 O(n) 的时间复杂度做到，因此在找分割点实现分区或者交换元素的时候，时间复杂度退化为 O(n²)，失去了快排的 O(nlogn) 的优势。

总而言之，快速排序依赖随机访问和高效交换，链表的结构限制了这两点。归并排序因其分治特性和指针操作的高效性，成为链表排序的标准方法。

归并排序的常规解法是自顶向下的递归实现，考虑到递归调用的栈空间，自顶向下归并排序的空间复杂度是 O(logn) ，其中 n 是递归的深度。如果要达到 O(1) 的空间复杂度，需要使用自底向上的实现方式。

先来看自顶向下的归并排序：

对链表自顶向下归并排序的步骤主要有三步

第一步：找到链表中间的节点，以中节点为分界，将链表拆分成两个子链表（子链表采用左闭右开的不变量法则）。寻找链表的中点可以通过双指针来实现，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。

第二步：对两个子链表分别排序。

第三步：将两个排序后的子链表合并，得到完整的排序后的链表。使用之前做过的一道题“合并两个有序链表”的做法，将两个有序的子链表进行合并。

上述三步骤通过递归来实现，终止条件是分割的子链表中的节点数为 0 或者为 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) {
        //自顶向下归并排序思想：
        return sortList(head, null);

    }

    public ListNode sortList(ListNode head, ListNode tail){
        if (head == null) {
            return head;
        }
        if(head.next == tail){
            head.next = null;
            return head;
        }
        //1.找到链表的中点（快慢指针思想）
        ListNode fast = head;
        ListNode slow = head;
        while(fast != tail){
            fast = fast.next;
            slow = slow.next;
            if(fast != tail){
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        //2.对两个子链表分别排序（递归）
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        //3.将两个排序后的子链表进行合并，得到完整的排序后的链表
        ListNode sortedList = merge(list1, list2);
        return sortedList;

    }

    public ListNode merge(ListNode list1, ListNode list2){
        ListNode dummy = new ListNode();
        ListNode curr = dummy;
        //两个链表都是非空的情况，需要合并排序
        while(list1 != null && list2 != null){
            int v1 = list1.val;
            int v2 = list2.val;
            if(v1 <= v2){
                curr.next = list1;
                list1 = list1.next;
            }else {
                curr.next = list2;
                list2 = list2.next;
            }
            curr = curr.next;
        }
        //只有一个链表非空，那么就不用合并了，直接取它的链表即可
        curr.next = (list1 == null) ? list2 : list1;
        return dummy.next;

    }
}

时间复杂度为 O(nlogn)，空间复杂度为 O(logn)

再来看自底向上的归并排序

整体的思想是：

1、计算链表长度

首先遍历整个链表，计算节点总数 length

2、初始化虚拟头节点

初始化虚拟头节点 dummy ，它的 next 指向原链表的 头节点 head

3、子链表长度循环

subLength 从 1 开始，每次 以 2 倍 的方式迭代

每次循环将链表分割成多个长度为 subLength 的子链表

4、分割

head1 为第一个子链表的头

移动到第一个子链表的末尾，断开连接

head2 为第二个子链表的头

移动到第二个子链表的末尾，断开连接

保存剩余链表的头 next 以便后续处理

5、合并

合并上述 的 两个子链表

将合并后的链表连接到已处理的部分后面

移动到剩余未处理的部分 next ，重复上述过程

示例代码：

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return head;
        }
        int length = 0;
        ListNode node = head;
        while (node != null) {
            length++;
            node = node.next;
        }
        ListNode dummyHead = new ListNode(0, head);
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            ListNode prev = dummyHead, curr = dummyHead.next;
            while (curr != null) {
                ListNode head1 = curr;
                for (int i = 1; i < subLength && curr.next != null; i++) {
                    curr = curr.next;
                }
                ListNode head2 = curr.next;
                curr.next = null;
                curr = head2;
                for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
                    curr = curr.next;
                }
                ListNode next = null;
                if (curr != null) {
                    next = curr.next;
                    curr.next = null;
                }
                ListNode merged = merge(head1, head2);
                prev.next = merged;
                while (prev.next != null) {
                    prev = prev.next;
                }
                curr = next;
            }
        }
        return dummyHead.next;
    }

    public ListNode merge(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode();
        ListNode curr = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                curr.next = list1;
                list1= list1.next;
            } else {
                curr.next = list2 ;
                list2 = list2 .next;
            }
            curr= curr.next;
        }
        curr.next = (list1 == null) ? list2 : list1;
        return dummy.next;
    }
}

时间复杂度为 O(nlogn)，空间复杂度为 O(1)。