思路:
归并排序
- 递归的终止条件是链表的节点个数小于或等于 1,即当链表为空或者链表只包含 11个节点时,不需要对链表进行拆分和排序。
- 找到链表重点,对链表进行拆分,分别排序,返回两个链表的首结点,对于链表中点的找法可以采用快慢指针,快指针一次走两步,满指针一次走一步,快指针走到最后一个节点的额时候慢指针所在位置为中点
- 最后合并连个有序链表
代码:
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;
}
}
网友评论