标签：归并排序，合并链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3] 输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]
示例 3：
输入：head = [] 输出：[]
提示：链表中节点的数目在范围 [0, 5 * 104] 内
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
思路：话不多说，直接上进阶解题思路，因为面试考官要的就是手撕进阶答法(百度是这样的)，排序O(nlogn)直接想到归并排序，两两一组不断合并，直到合并到长度为链表长度。注意一组的长度是2倍递增的，例如：1 1->2 2 2->4....用到了leetcode21.合并两个有序列表-CSDN博客知识。
public ListNode sortList(ListNode head) {
// 0/1个节点
if(head==null||head.next==null)
return head;
// 统计节点长度
int length=0;
ListNode count=head;
while(count!=null) {
length++;
count=count.next;
}
// 两两一组合并 为每一组的开头和结尾都设置一个指针
ListNode lis1_start=head;
ListNode lis1_stop=head;
ListNode lis2_start=head;
ListNode lis2_stop=head;
ListNode cur=head;// cur往下找新的组
ListNode node=new ListNode(0,head); // node作为虚拟头节点，后面是连接排好的组
ListNode end=node;// 和node搭配 表示当前连接好的组的结尾节点
// 一直合并到组长度为length
for(int sum=1;sum<length;sum*=2){
lis1_start=node.next;
lis1_stop=node.next;
lis2_start=node.next;
lis2_stop=node.next;
cur=node.next;
end=node;
//执行 n/sum次
while(cur!=null){
lis1_start=cur;
lis1_stop=cur;
for(int i=1;i<sum&&lis1_stop!=null;i++){
lis1_stop=lis1_stop.next;
}
if(lis1_stop!=null)
lis2_start=lis1_stop.next;
else
lis2_start=null;
lis2_stop=lis2_start;
if(lis1_stop!=null)
lis1_stop.next=null;
for(int i=1;i<sum&&lis2_stop!=null;i++){
lis2_stop=lis2_stop.next;
}
if(lis2_stop!=null){
cur=lis2_stop.next;
lis2_stop.next=null;
}
else
cur=null;
// sum*2
ListNode dummy=mergeTwoLists(lis1_start,lis2_start);
end.next=dummy;
while(end.next!=null)
end=end.next;
}
}
return node.next;
}
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode ret=new ListNode(0);
ListNode head=ret;
while(list1!=null||list2!=null){
if(list1==null||list2!=null&&list2.val<=list1.val){
ret.next =list2;
list2=list2.next;
}
else if(list2==null||list1!=null&&list1.val<=list2.val){
ret.next =list1;
list1=list1.next;
}
ret=ret.next;
}
return head.next;
}