148、排序链表(中等)

对链表进行排序

1 简单暴力法

简单粗暴，定义超大空间直接利用数组排序：

class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null ) return null;
        ListNode start = head;
        int m=(int) Math.pow(10,4)*5;
        int[] res = new int[m];
        
        int i = 0;
        while(start != null){
            res[i++] = start.val;
            start = start.next;
        }
        Arrays.sort(res,0,i);
        ListNode dummpy = new ListNode(0);
        start = dummpy;
        for(int j = 0; j< i; j++){
            ListNode tmp = new ListNode(res[j]);
            start.next = tmp;
            start = start.next;
            
        }
        return dummpy.next;
    }
}

这样居然速度超过98%的用户，但是空间却用得很多，因为很多空间都用不着

当然也可以不定义这么大的int数组

class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null ) return null;
        ListNode start = head;
        List<Integer> res = new ArrayList<>();
        
        while(start != null){
            res.add(start.val);

            start = start.next;
        }


        //res.sort(Comparator.naturalOrder());
        Collections.sort(res);
        ListNode dummpy = new ListNode(0);
        start = dummpy;
        for(Integer val : res){
            ListNode tmp = new ListNode(val);
            start.next = tmp;
            start = start.next;
            
        }
        return dummpy.next;
    }
}

但其实这种方法，只优化了链表数量少时用到的空间，对于大数据量的节点，反倒时间消耗上增加了很多，空间也没优化。

2 归并排序

class Solution {
    public ListNode sortList(ListNode head) {
        return mergesort(head);
    }

    public ListNode mergesort(ListNode head){
        //利用快慢指针，找到中间的值
        //如果节点为空或者只有一个节点，直接返回;
        if(head == null || head.next == null){
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next.next;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //排序右边
        ListNode r = mergesort(slow.next);
        //断开链表，返回的标志是null
        slow.next = null;
        ListNode l = mergesort(head);

        //合并左右链表
        return mergeLinked(l,r);
    }

   //合并两个有序链表返回
    public ListNode mergeLinked(ListNode list1, ListNode list2){
        ListNode dummpy = new ListNode(0);
        ListNode start = dummpy;
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                start.next = list1;
                list1 = list1.next;
            }else{
                start.next = list2;
                list2 = list2.next;
            }
            start = start.next;
        }

        if(list1 != null ){
            start.next = list1;
        }
        if(list2 != null){
            start.next = list2;
        }
        return dummpy.next;
    }
}

3 快速排序

参考：Java实现单链表的快速排序和归并排序 - morethink - 博客园 (cnblogs.com)

class Solution {
    public ListNode sortList(ListNode head) {
        quicksort(head,null);
        return head;
    }

    public static void  quicksort(ListNode head,ListNode end){
        if(head != end) {
            ListNode node = partition(head,end);
            quicksort(head,node);
            quicksort(node.next,end);
        }
    }

    //划分链表
    public static ListNode partition(ListNode head, ListNode end){

        //就选定第一个元素为key
        ListNode key = head;
        ListNode p1 = head,p2 = head.next;

        //保证head-p1之间的值比key小 p1-p2之间的值比key大
        while(p2 !=null){
            //如果p2的小于key那么将，p2的值与p1交换
            if(p2.val < key.val){
                //p1向前走一步，现在值大于key
                p1 = p1.next;
                int tmp = p2.val;
                p2.val = p1.val;
                p1.val = tmp;
            }
            p2 = p2.next;
        }
        //当有序时，不交换p1和key值
        if (p1 != head) {
            int temp = p1.val;
            p1.val = head.val;
            head.val = temp;
        }
        return p1;
    }
}

提交后居然超时了，上述代码知识交换了节点的值没有 没有断开节点。

不过也学习了一下链表的快速排序