Sort List

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

今天并沒有寫出通過(guò)測(cè)試的代碼...

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

明天試試快速和歸并

對(duì)于數(shù)組來(lái)說(shuō)，常用的排序方法有7種

• 插入排序（直接插入和希爾）
• 選擇排序（簡(jiǎn)單選擇，堆）
• 交換排序（冒泡，快速）
• 歸并排序

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

花點(diǎn)時(shí)間將基本能看到的方法全部寫一遍

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;
    }
    
    /*
     * 冒泡排序，先寫思路
     * 先判斷進(jìn)來(lái)的節(jié)點(diǎn)是否為空，是則返回null
     * 之后判斷進(jìn)來(lái)節(jié)點(diǎn)的next字段是否為空，為空返回head
     * 之后順次交換鏈表中亂序的相鄰組合，設(shè)置flag，從開頭到結(jié)尾都
     * 一旦發(fā)生交換，則設(shè)為false，說(shuō)明有交換，可能仍然是亂序
     * 直到某次從頭到尾的掃描都沒有發(fā)生交換
     * 則說(shuō)明已經(jīng)完成了排序，時(shí)間復(fù)雜度o(n^2）
     * 穩(wěn)定排序
     * 測(cè)試結(jié)果..當(dāng)然是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;
            //確定第一個(gè)節(jié)點(diǎn)
            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個(gè)節(jié)點(diǎn)有序，即 1-2，3-4，5-6，。。。。。
     * 對(duì)每相鄰的兩段有序的節(jié)點(diǎn)歸并，使得相鄰的兩段整個(gè)有序；
     * 重復(fù)2），直到整個(gè)鏈表有序；
     * 時(shí)間復(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);
    }
}