归并排序
class Solution {
public ListNode sortList(ListNode head) {
return sortList(head, null);
}
//对收尾为head和tail的链表进行排序
public ListNode sortList(ListNode head, ListNode tail) {
if (head == null) {
return null;
}
//区间范围,前闭后开 [mid, tail),tail不包含在内。
//如果只有一个结点了就不需要再拆了
if (head.next == tail) {
head.next=null;
return head;
}
//找到中间结点
//快指针一次走两步,慢指针一次走一步,快指针到链表末尾时候
//慢指针指向链表中间位置
ListNode quick=head,slow=head;
while (quick!=tail){
quick=quick.next;
slow=slow.next;
//防null,直到quick走到最后一个结点
if (quick!=tail){
quick=quick.next;
}
}
//区间范围,前闭后开 [mid, tail),tail不包含在内。
ListNode listNode1 = sortList(head, slow);
ListNode listNode2 = sortList(slow, tail);
//合并两个有序链表,返回合并链表头结点
ListNode res=merge(listNode1,listNode2);
return res;
}
//合并两个有序链表,返回合并链表头结点
private ListNode merge(ListNode listNode1, ListNode listNode2) {
ListNode pre=new ListNode(0);
ListNode curr=pre,temp1=listNode1,temp2=listNode2;
while (temp1!=null&&temp2!=null){
if (temp1.val<temp2.val){
curr.next=temp1;
temp1=temp1.next;
}else {
curr.next=temp2;
temp2=temp2.next;
}
curr=curr.next;
}
if (temp1==null){
curr.next=temp2;
}
if (temp2==null){
curr.next=temp1;
}
return pre.next;
}
}