Sort List

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

今天并沒有寫出通過測試的代碼...

寫了一個冒泡排序的，效率明顯不夠

明天試試快速和歸并

對于數(shù)組來說随常，常用的排序方法有7種

• 插入排序（直接插入和希爾）
• 選擇排序（簡單選擇拓萌，堆）
• 交換排序（冒泡尝抖，快速）
• 歸并排序

推廣到鏈表柳洋，應(yīng)該很多都可以做到

花點時間將基本能看到的方法全部寫一遍

package Sort.List;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    /*
     * Sort a linked list in O(n log n) time using constant space complexity.

     */
    
    public ListNode sortList(ListNode head) {
        maopaoList(head);
        return null;
    }
    
    /*
     * 冒泡排序锁蠕，先寫思路
     * 先判斷進來的節(jié)點是否為空裙士，是則返回null
     * 之后判斷進來節(jié)點的next字段是否為空征堪，為空返回head
     * 之后順次交換鏈表中亂序的相鄰組合，設(shè)置flag背桐，從開頭到結(jié)尾都
     * 一旦發(fā)生交換优烧，則設(shè)為false，說明有交換链峭，可能仍然是亂序
     * 直到某次從頭到尾的掃描都沒有發(fā)生交換
     * 則說明已經(jīng)完成了排序畦娄，時間復(fù)雜度o(n^2）
     * 穩(wěn)定排序
     * 測試結(jié)果..當然是Time Limit Exceeded
     */
    
    public ListNode maopaoList(ListNode head){

        if(head == null)
            return null;
        if(head.next == null )
            return head;
        
        boolean  flag = false;
        ListNode firstNode , temp , preNode;
        
        while(true){
            flag = true;
            //確定第一個節(jié)點
            if(head.val > head.next.val){
                firstNode = head.next ;
                preNode = head.next;
                temp = head.next.next;
                head.next.next = head;
                head.next = temp;

            }else{
                firstNode = head;
                preNode = head;
                head = head.next;
            }
            while(head.next != null){
                if(head.val > head.next.val){
                    temp = head.next.next;
                    preNode.next = head.next;
                    head.next.next = head;
                    head.next = temp;               
                    preNode = preNode.next;
                    flag = false;
                }else{
                    preNode = head;
                    head = head.next;
                }
            }
            if(flag)
                break;
            head = firstNode;
        }
        
        //print(firstNode);
        return firstNode;

    }
    

    
    /*
     * 類似歸并排序的方法
     * 首先讓每相鄰的2個節(jié)點有序，即 1-2，3-4熙卡，5-6杖刷，。驳癌。滑燃。。颓鲜。
     * 對每相鄰的兩段有序的節(jié)點歸并表窘，使得相鄰的兩段整個有序；
     * 重復(fù)2）甜滨，直到整個鏈表有序蚊丐；
     * 時間復(fù)雜度o(n*logn)
     * 
     * 思路和上面的基本一致
     * 
     */
    
    public ListNode guibingList(ListNode head){
        if(head == null)
            return null;
        
        if(head.next == null)
            return head;
        
        //明天再戰(zhàn)
        
        return null;
    }
    
    public void print(ListNode head){
        while(head != null){
            System.out.print(head.val + "  ");
            head = head.next;
        }
    }
    
    public Solution(ListNode head){
        sortList(head);
    }
    
    public static void main(String[] args){
        ListNode first = new ListNode(8);
        ListNode second = new ListNode(7);      
        ListNode third = new ListNode(4);
        ListNode fourth = new ListNode(9);
        
        first.next = second;
        second.next = third;
        third.next = fourth;
        
        
        Solution test = new Solution(first);
    }
}