在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
首先看一下归并排序，其思路是先将所有元素两两划分为一组，然后递归合并，合并就相当于将两个排序好的链表合并为一个。这样最终我们就可以将链表排序好了。那么关键所在就是先分裂，在合并。代码如下所示：
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
// 使用两个指针，一快一慢，当快指针走到链表尾部时，慢指针正好到中间位置。
ListNode prev = null, slow = head, fast = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
//prev表示第一个链表的尾部，所以指向空。slow为第二个指针的头部
prev.next = null;
// 继续分裂
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
// 当分裂到最后每个元素时，开始两两合并
return merge(l1, l2);
}
//将两个有序链表合并的函数
ListNode merge(ListNode l1, ListNode l2) {
ListNode l = new ListNode(0), p = l;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if (l1 != null)
p.next = l1;
if (l2 != null)
p.next = l2;
return l.next;
}
另外一种方法就是快速排序法，快速排序的思路就是先将链表根据某个基础元素值分为两部分，比他大的和比他小的，然后一直这样分类下去，最后在进行合并即可，代码如下所示：
ListNode sortList(final ListNode h){
if(h == null || h.next == null)
return h;
/*split into three list*/
ListNode fakesmall = new ListNode(0), small = fakesmall;
ListNode fakelarge = new ListNode(0), large = fakelarge;
ListNode fakeequal = new ListNode(0), equal = fakeequal;
ListNode cur = h; // pivot is h.
while(cur != null){
if(cur.val < h.val){
small.next = cur;
small = small.next;
}
else if(cur.val == h.val){
equal.next = cur;
equal = equal.next;
}
else{
large.next = cur;
large = large.next;
}
cur = cur.next;
}
// put an end.
small.next = equal.next = large.next = null;
// merge them and return . merge reusing below one. merge for quicksort should be simplified.
return merge(merge(sortList(fakesmall.next), sortList(fakelarge.next)),fakeequal.next) ;
}
ListNode merge(ListNode l1, ListNode l2) {
ListNode l = new ListNode(0), p = l;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if (l1 != null)
p.next = l1;
if (l2 != null)
p.next = l2;
return l.next;
}
