在 O(n log n) 時(shí)間復(fù)雜度和常數(shù)級(jí)空間復(fù)雜度下迅办，對(duì)鏈表進(jìn)行排序。
示例 1:
輸入: 4->2->1->3
輸出: 1->2->3->4
示例 2:
輸入: -1->5->3->4->0
輸出: -1->0->3->4->5
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
return head == null ? null : mergeSort(head);
}
private ListNode mergeSort(ListNode head) {
if (head.next == null){
return head;
}
ListNode s = head,f = head,pre = null;
//找中點(diǎn)
while (f != null && f.next != null){
pre = s;
f = f.next.next;
s = s.next;
}
pre.next = null;//斷開(kāi)
ListNode l = mergeSort(head);
ListNode r = mergeSort(s);
return merge(l,r);
}
//并
private ListNode merge(ListNode l, ListNode r) {
ListNode dummyHead = new ListNode(0);
ListNode cur = dummyHead;
while (l != null && r !=null){
if (l.val < r.val){
cur.next = l;
cur = cur.next;
l = l.next;
}
else {
cur.next = r;
cur = cur.next;
r = r.next;
}
}
//處理剩下的鏈表數(shù)據(jù)
if (l != null){
cur.next = l;
}
if (r != null){
cur.next = r;
}
return dummyHead.next;
}
}
