一.题目描述
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
输入：head = [4,2,1,3]
输出：[1,2,3,4]
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
输入：head = []
输出：[]
提示：
链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105
二.题目解析
public ListNode sortList1(ListNode head) {
/*暴力法.时间复杂度O(nlogn),空间复杂度O(n)
* */
ListNode cur = head;
int count = 0,i;
//第一次遍历获得所有的节点数
while (cur != null){
count++;
cur = cur.next;
}
//第二次遍历把节点值存储在数组里
int[] arr = new int[count];
for (cur = head,i = 0; i < count; i++,cur = cur.next) {
arr[i] = cur.val;
}
//对数组进行排序
Arrays.sort(arr);
//第三次遍历更新链表的值
for (cur = head,i = 0; i < count; i++,cur = cur.next) {
cur.val = arr[i];
}
return head;
}
2.根据时间复杂度想到二分法，从而联想到归并排序
分：把原链表分为两个子链表的归并排序
治：在切割后的子链表只要满足节点个数大于1的时候就一直分；
合：合并切割后的子链表为有序链表，依次向上合并
对数组做归并排序的空间复杂度为 O(n)，分别由merge部分新开辟数组O(n)和递归函数调用O(logn)组成，
根据链表特性：
数组额外空间：链表可以通过修改引用来更改节点顺序，无需像数组一样开辟额外空间；
递归额外空间：递归调用函数将带来O(logn)的空间复杂度，因此若希望达到O(1)空间复杂度，则只能使用迭代法；
使用递归实现自顶向下的归并排序：
public ListNode sortList(ListNode head) {
/*归并排序-递归法.时间复杂度O(nlogn),空间复杂度O(logn)
* */
//链表只有一个节点需要归并排序，那么直接返回即可
if(head == null || head.next == null){
return head;
}
///分环节，只要满足大于1个节点就一直分
//快慢指针法定位链表中点（奇数个的话slow正好定位到中点，偶数个的话定位到中点的左边那个节点）
ListNode fast = head.next,slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
//newHead指向“分”后的第二个链表头结点
ListNode newHead = slow.next;
//断链，实现“分”
slow.next = null;
//before指向前半部分归并排序之后的链表头结点
ListNode before = sortList(head);
//after指向后半部分归并排序之后的链表头结点
ListNode after = sortList(newHead);
///merge环节
//将两个排序链表merge，转化为一个排序链表
//建立虚拟头结点
ListNode dummyHead = new ListNode(-1,null);
//cur指向新链表的最后一个节点（merge的过程中持续更新）
ListNode cur = dummyHead;
//如果两个链表都没到结尾
while (before != null && after != null){
if(before.val <= after.val){
cur.next = before;
before = before.next;
}else{
cur.next = after;
after = after.next;
}
cur = cur.next;
}
//最后只需要接上较长的那个链表剩余部分即可
cur.next = before == null ? after : before;
return dummyHead.next;
}
3.我们可以使用迭代来代替递归，实现自底向上的归并排序：
public ListNode sortList2(ListNode head) {
/*归并排序-迭代法.时间复杂度O(nlogn),空间复杂度O(1)
* */
int length = getLength(head);
ListNode dummy = new ListNode(-1);
dummy.next = head;
for(int step = 1; step < length; step*=2){ //每次要merge的两个链表元素个数依次是1,2,4...
//每次变换步长，pre指针和cur指针都初始化在链表头
ListNode pre = dummy;
ListNode cur = dummy.next;
//cur为未处理链表的头结点，while循环不断把链表按照step往下分割，merge，直到待处理链表节点是null
while(cur!=null){
//每次循环处理step*2个节点
ListNode h1 = cur; //第一部分头指向上轮merge后剩余待处理链表的头结点
ListNode h2 = split(h1,step); //断链后的第二部分头
//至此原链表被分为merge链表h1,merge链表h2,剩余链表cur
cur = split(h2,step);
//h1（节点个数step个）,h2（节点个数step个）两两merge
//temp指向这两个链表merge后的头结点
ListNode temp = merge(h1,h2);
//将前面merge好的的部分 与 此次merge的两个链表连接。此时原链表被分为已完成merge的链表，未处理的链表
pre.next = temp;
//pre指针指向已完成merge的最后一个节点（方便连接下轮merge的头结点）
while(pre.next!=null){
pre = pre.next;
}
}
}
return dummy.next;
}
public int getLength(ListNode head){
//获取链表长度
int count = 0;
while(head!=null){
count++;
head=head.next;
}
return count;
}
public ListNode split(ListNode head,int step){
//断链操作（从head开始计算step个节点后，开始断链）， 返回第二部分链表头
if(head==null) return null;
ListNode cur = head;
for(int i=1; i<step && cur.next!=null; i++){
cur = cur.next;
}
ListNode right = cur.next;
cur.next = null; //切断连接
return right;
}
public ListNode merge(ListNode h1, ListNode h2){
//合并两个有序链表
ListNode head = new ListNode(-1);
ListNode p = head;
while(h1!=null && h2!=null){
if(h1.val < h2.val){
p.next = h1;
h1 = h1.next;
}
else{
p.next = h2;
h2 = h2.next;
}
p = p.next;
}
if(h1!=null) p.next = h1;
if(h2!=null) p.next = h2;
return head.next;
}
