Sort a linked list in O(n log n) time using constant space complexity.
这道题要求用nlogn的时间复杂度去做，代码如下：
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9 public class Solution { 10 public ListNode sortList(ListNode head) { 11 if(head==null||head.next==null) return head;//corner case:if the List is null or the length of List is just one. 12 ListNode fast = head,slow = head,prev = null; 13 while(fast!=null&&fast.next!=null){//find the middle of the listnode 14 prev = slow; 15 slow = slow.next; 16 fast = fast.next.next; 17 } 18 //divide the List into two parts 19 prev.next = null; 20 //recursive the sortList 21 ListNode l1=sortList(head); 22 ListNode l2=sortList(slow); 23 //conquer two parts together 24 return combine(l1,l2); 25 } 26 public ListNode combine(ListNode l1,ListNode l2){ 27 ListNode l = new ListNode(0),p = l; 28 while(l1!=null&&l2!=null){ 29 if(l1.val<=l2.val){ 30 p.next = l1; 31 l1 = l1.next; 32 }else{ 33 p.next = l2; 34 l2 = l2.next; 35 } 36 p = p.next; 37 if(l1!=null){ 38 p.next = l1; 39 } 40 if(l2!=null){ 41 p.next = l2; 42 } 43 } 44 return l.next; 45 } 46 } 47 //
本题是典型的merge sort，只不过输入的数据是链表而不是数组了，那么我们需要每次找到中间的位置，要用到快慢指针，所以每次寻找中间位置的时间复杂度是O（n），总共需要运行logn次，所以总的时间复杂度是nlongn