题目描述：
解题思路：
题目的进阶问题要求达到 O(nlogn) 的时间复杂度和O(1) 的空间复杂度，时间复杂度是 O(nlogn) 的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是 O(n^2)，其中最适合链表的排序算法是归并排序。
先回忆一下自顶向下归并：
归并排序排序采用分治算法，将已有序的子序列合并得到完全有序的序列。
?
在本题中，先找到链表的中间节点（可以用快慢指针），将链表分为两个部分，再分别二分左右两边的链表，直到节点为空或者只剩一个节点时结束。这里可以采用递归方式分割。分割完成后就可以合并各个子链表。
代码实现如下：
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;//只保留head到mid的前一个节点
return head;
}
ListNode slow = head,fast = head;//快慢指针，找到中间节点
while (fast != tail) {
fast = fast.next;
slow = slow.next;
if (fast != tail) {
fast = fast.next;
}
}
ListNode mid = slow;
ListNode head1 = sortList(head,mid);//开始递归，由上面的代码铺垫，这里的mid会被置为空
ListNode head2 = sortList(mid,tail);//这里的mid相当于头结点
ListNode new_head = merge(head1,head2);合并子序列
return new_head;
}
public ListNode merge(ListNode head1,ListNode head2) {
ListNode dummyHead = new ListNode(-1);//傀儡节点
ListNode tmp = dummyHead,tmp1 = head1,tmp2 = head2;
while (tmp1 != null && tmp2 != null) {
if (tmp1.val <= tmp2.val) {
tmp.next = tmp1;
tmp1 = tmp1.next;
} else {
tmp.next = tmp2;
tmp2 = tmp2.next;
}
tmp = tmp.next;
}
if (tmp1 == null) tmp.next = tmp2;
else if (tmp2 == null) tmp.next = tmp1;
return dummyHead.next;
}
}由于自顶向下归并用到了递归方法，空间复杂度达到O(logn)，不符合题目要求的O(1),所以这里要采取自底向上的非递归排序方法。我们可以采用迭代的方法从最小的单元开始合并，合并后的新的子序列继续合并，直到子序列长度达到链表原始长度。所以第一步我们要求的是链表的长度，然后根据长度迭代时间复杂度O(N)。每次长度都会缩小两倍，时间复杂度O(logN)。完成以上步骤后时间复杂度为O(nlogn）,空间复杂度只有定义的变量，是常数复杂度O(1)。
代码实现如下：
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);
//拆分链表成若干个子链表，子链表长度从1开始，后面是2、4、8、16...直到达到length。
for (int subLen = 1;subLen < length;subLen <<= 1) {
ListNode prev = dummyHead; //prev负责连接每个有序子链表
ListNode curr = dummyHead.next; //拆分链表开始的位置
while (curr != null) {//如果没有拆分结束
ListNode head1 = curr; //记录第一个子链表
for (int i = 1;i < subLen && curr != null && curr.next != null;i++) {
curr = curr.next;
}
ListNode head2 = curr.next; //第一个子链表长度达到subLen，下一个节点是第二个链表的起始位置
curr.next = null; //断开第一个和第二个链表的连接
curr = head2;
for (int i = 1;i < subLen && curr != null && curr.next != null;i++) {
curr = curr.next; //开始拆分第二个长度为subLen的链表
}
ListNode next = null;
if (curr != null) {
next = curr.next; //记录后面剩下的链表的位置
curr.next = null; //断开第二个链表与后面的连接，这样head1、head2都是两个独立的链表
}
ListNode merge = mergeTwoLists(head1,head2);//排序后合并成有序链表
prev.next = merge; //连接上新的子链表的头结点
while (prev.next != null) {
prev = prev.next; //走到目前已经排好序的链表的末尾，准备下一次连接新的子链表
}
curr = next; //curr从第三个第三个链表的头开始走，准备和第四个链表排序后合并
}
}
return dummyHead.next;
}
public ListNode mergeTwoLists(ListNode head1,ListNode head2) {//合并子链表
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (head1 != null && head2 != null) { //只要有一个链表为空则退出循环
if (head1.val < head2.val) {
cur.next = head1;
head1 = head1.next;
} else {
cur.next = head2;
head2 = head2.next;
}
cur = cur.next;
}
if (head1 == null) cur.next = head2; //把没走完的链表的剩下部分连接上
else if (head2 == null) cur.next = head1;
return dummy.next;
}
}