LeetCode之路1.5 Sort List

Sort List

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

今天并没有写出通过测试的代码...

写了一个冒泡排序的，效率明显不够

明天试试快速和归并

对于数组来说，常用的排序方法有7种

• 插入排序（直接插入和希尔）
• 选择排序（简单选择，堆）
• 交换排序（冒泡，快速）
• 归并排序

推广到链表，应该很多都可以做到

花点时间将基本能看到的方法全部写一遍

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;
    }
    
    /*
     * 冒泡排序，先写思路
     * 先判断进来的节点是否为空，是则返回null
     * 之后判断进来节点的next字段是否为空，为空返回head
     * 之后顺次交换链表中乱序的相邻组合，设置flag，从开头到结尾都
     * 一旦发生交换，则设为false，说明有交换，可能仍然是乱序
     * 直到某次从头到尾的扫描都没有发生交换
     * 则说明已经完成了排序，时间复杂度o(n^2）
     * 稳定排序
     * 测试结果..当然是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;
            //确定第一个节点
            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个节点有序，即 1-2，3-4，5-6，。。。。。
     * 对每相邻的两段有序的节点归并，使得相邻的两段整个有序；
     * 重复2），直到整个链表有序；
     * 时间复杂度o(n*logn)
     * 
     * 思路和上面的基本一致
     * 
     */
    
    public ListNode guibingList(ListNode head){
        if(head == null)
            return null;
        
        if(head.next == null)
            return head;
        
        //明天再战
        
        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);
    }
}