T148、排序链表

在 O(n log n) 时间复杂度复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5

解

使用一个list保存所有链表的值，然后对list进行排序，将排序之后的值依次放回原链表即可。

   public ListNode sortList(ListNode head) {
        List<Integer> vals = new ArrayList<>();
        ListNode temp = head;
        while(temp != null){
            vals.add(temp.val);
            temp = temp.next;
        }
        Collections.sort(vals);
        temp = head;
        int i = 0;
        while(temp != null){
            temp.val = vals.get(i++);
            temp = temp.next;
        }
        return head;
    }

解2

归并链表排序方法

   public ListNode sortList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        //分解链表
        //快慢指针找到链表中点
        ListNode fast = head.next, slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode temp = slow.next;
        slow.next = null;
        ListNode left =  sortList(head);
        ListNode right = sortList(temp);

        //合并
        ListNode dummpy = new ListNode(0);
        ListNode res = dummpy;
        while(left != null && right != null){
            if(left.val < right.val){
                dummpy.next = left;
                left = left.next;
            }else{
                dummpy.next = right;
                right = right.next;
            }
            dummpy = dummpy.next;
        }
        dummpy.next = left != null ? left : right;
        return res.next;
    }