排序
桶排序
sortList(head)
│
┌────────────┴─────────────┐
│ 是否只有 0 或 1 个节点？ │
└───────┬────────┬─────────┘
│是 │否
▼ ▼
返回 head 找中点 slow
pre.next = null
│
▼
┌───────────────┴───────────────┐
│ │
sortList(leftHalf) sortList(rightHalf)
│ │
┌────┴────┐ ┌────┴────┐
│ 递归返回 │ │ 递归返回 │
│ 有序左链 │ │ 有序右链 │
└────┬────┘ └────┬────┘
▼ ▼
┌──────────────┴──────────────┐
│ merge(有序左链, 有序右链) │
└──────────────┬──────────────┘
▼
返回合并后的有序链表 sortList([4,2,1,3])
/ \
sortList([4,2]) sortList([1,3])
/ \ / \
[4] [2] [1] [3]
| | | |
merge([4],[2])= [2,4] merge([1],[3])= [1,3]
\ /
merge([2,4],[1,3])
= [1,2,3,4]class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null){
return head;
}
//找中点
ListNode slow = head,fast = head,pre = null;
while(fast != null && fast.next != null){
pre = slow;
fast = fast.next.next;
slow = slow.next;
}
pre.next = null;
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
return merge(l1,l2);
}
ListNode merge(ListNode l1,ListNode l2){
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = (l1 == null) ? l2 : l1;
return dummy.next;
}
}