sort list

https://leetcode.com/problems/sort-list/
给定一个链表，给链表排序，用nlogn的时间复杂度，并且使用O(1)的空间

思路

经典题目，nlogn的时间复杂度的排序算法——快排，归并排序，堆排序。快排的基本思路是需要进行元素的对调。针对这种链表的排序，天然优势用归并排序

先找到链表的中点，然后对左边部分递归排序，然后怼右边部分递归排序，然后把左边的有序结果和右边的有序结果合并

   public ListNode sortList2(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode slow = head,fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode firsthalf = head;
        ListNode secondhalf = slow.next;
        slow.next = null;
//        if(firsthalf != secondhalf){
            firsthalf = sortList2(firsthalf);
            secondhalf = sortList2(secondhalf);
//        }

        return mergeTwoLists(firsthalf,secondhalf);
    }

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(-1);
        ListNode head = new ListNode(-1);
        head = res;

        while (l1 != null && l2 != null) {

            int vv = l1.val >= l2.val ? l2.val : l1.val;
            ListNode tmp = new ListNode(vv);
            if (l1.val >= l2.val) {
                l2 = l2.next;
            } else {
                l1 = l1.next;

            }
            res.next = tmp;
            res = res.next;
        }

        if (l1 != null) {
            res.next = l1;
        }

        if (l2 != null) {
            res.next = l2;
        }
        return head.next;
    }