148.Sort List (M)

https://leetcode.com/problems/sort-list/

1.Description(Medium)

Sort a linked list in O(n_log_n) time using constant space complexity.

Example

Given1->3->2->null, sort it to1->2->3->null.

2.Code

排序要求O(nlogn)的时间,就是Quicksort, Mergesort, Heapsort

没有n次new语句的就是constant space.

Merge Sort：

1> 找中点 middle,断开前后两个链表

2> Recursive (Divided left right)

3> Merge (left,right)

public ListNode sortList(ListNode head){
           if(head==null || head.next==null){
               return head;
           }

           ListNode middle=findMiddle(head);
           ListNode right=sortList(middle.next);
           middle.next=null;
           ListNode left=sortList(head);

           return merge(left,right);

   }

   public ListNode findMiddle(ListNode head){
           if(head==null){
               return null;
           }
           ListNode slow=head;
           ListNode fast=head.next;
           while(fast!=null && fast.next!=null){
               fast=fast.next.next;
               slow=slow.next;
           }
           return slow;
   }

   public ListNode merge(ListNode left,ListNode right){
           ListNode dummy=new ListNode(0);
           ListNode temp=dummy;

           while(left!=null && right!=null){
               if(left.val<right.val){
                   temp.next=left;
                   left=left.next;
               }else{
                   temp.next=right;
                   right=right.next;
               }
               temp=temp.next; //caution
           }
           if(left!=null){
               temp.next=left;
           }
           if(right!=null){
               temp.next=right;
           }
           return dummy.next;
   }