题目描述
?
示例分析
题目要求
?
一看见时间复杂度为O(N*logN)，而处于这个时间复杂度的排序只有三个：堆排、快排、归并排序，快排最坏情况下，是O(N^2)，而堆排不适合链表的排序，所以只剩下归并排序了。?
??方法一：自顶而下（递归）
自顶而下的方式，就是将链表在递出去的过程中不断拆分成两半，直到只剩下最后两个结点的时候才开始归回来合并，在归回来的时候，左右两个序列段都已经分别有序了，所以合并过程就是将两个有序序列段合并。但是这样做还是达不到完成这个题的要求，这里只是提供一种递归的思路，后面会给出迭代的思路。
代码实现
public ListNode sortList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode slow = head;
ListNode fast = head.next;
//快慢指针来分割链表
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode midR = slow.next;
slow.next = null;//将中间结点置空是下次递归 return 的必要条件
ListNode left = sortList(head);
ListNode right = sortList(midR);
//合并
ListNode newHead = new ListNode(0);
ListNode prev = newHead;;
while(left != null && right != null) {
if(left.val <= right.val) {
prev.next = left;
left = left.next;
} else {
prev.next = right;
right = right.next;
}
prev = prev.next;
}
//走到这里，两个有序序列，一个为空，一个不为空，把不为空的接在prev的后面
prev.next = (left != null ? left : right);
return newHead.next;
}画图分析
上图分析了左半部分递出去的过程，2和5合并完之后成为一个有序序列段，而 midR 这一边是一个单独的只有一个结点的有序序列段，所以就印证了前面的解释。
复杂度分析
- 时间复杂度：O(N*logN) ，就是归并排序的时间复杂度。
- 空间复杂度：O(logN)，每一层的合并都用到了辅助结点，所以空间复杂度就是树的高度。
?方法二：自底而上（迭代）
自顶而下为什么做不到常数个空间的空间复杂度呢，因为每递归一次，就要开辟一个辅助的栈空间，并且先执行一个函数的左，右边还没执行，所以栈空间就没有被回收，就必然导致空间复杂度较迭代来说要高。迭代的方式不像递归那样先操作整条链表，再不断细分，而是先两两有序，再四个四个有序...，最后当subLen = 链表长度的一半时，执行完本次循环，就全部有序。
代码实现
public ListNode sortList(ListNode head) {
if (head == null) {
return head;
}
int len = 0;
ListNode node = head;
while (node != null) {
len++;
node = node.next;
}
ListNode newHead = new ListNode(0, head);
//每次循环不断让左右序列扩大两倍
for (int subLen = 1; subLen < len; subLen <<= 1) {
ListNode prev = newHead;
ListNode cur = newHead.next;
while (cur != null) {
ListNode head1 = cur;
//移动到左子序列的尾巴
for (int i = 1; i < subLen && cur.next != null; i++) {
cur = cur.next;
}
ListNode head2 = cur.next;
//分割
cur.next = null;
cur = head2;
//移动到右子序列的尾巴
for (int i = 1; i < subLen && cur != null && cur.next != null; i++) {
cur = cur.next;
}
//用next记录下一次待合并的两序列中左序列的头
ListNode next = null;
if (cur != null && cur.next != null) {
next = cur.next;
cur.next = null;
}
ListNode merged = merge(head1, head2);
//将合并的序列串在辅助结点之后
prev.next = merged;
while (prev.next != null) {
prev = prev.next;
}
cur = next;
}画图分析
从图中可以明显看出迭代与递归的区别，也印证了前面说的先两两有序，再四个四个有序，当subLen = 1/2 len 的时候，执行完本次循环就全部有序。且迭代真正做到了开辟常数个栈空间。
复杂度分析
- 时间复杂度： O(N*logN)
- 空间复杂度： O(1)
本篇完！！！