Sort List

https://leetcode.com/problems/sort-list/
对于整数构成的链表，将其排序 O(NLogN)时间复杂度，O(1)空间复杂度

• 思路
  归并思路，因为链表特有属性，无法进行堆排序和快排

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

        slow.next = null;

        fastHead = sortList(fastHead);
        slowHead = sortList(slowHead);
        return mergeList(fastHead, slowHead);
    }

    //merge 两个有序链表
    public ListNode mergeList(ListNode list1, ListNode list2) {

        ListNode res = new ListNode(-1);
        ListNode head = res;

        while (list1 != null && list2 != null) {

            if (list1.val > list2.val) {
                head.next = new ListNode(list2.val);
                list2 = list2.next;
            } else {
                head.next = new ListNode(list1.val);
                list1 = list1.next;
            }
            head = head.next;
        }

        if (list1 != null) {
            head.next = list1;
        }

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

• 插入排序思路
  时间复杂度O(N2)，空间复杂度O(1)
  单独开一个res链表，维持这个res是有序的~ 并且保证从head遍历的val能插入到此链表中

 public ListNode insertionSortList(ListNode head) {

        //结果链表
        ListNode res = new ListNode(-1);

        ListNode curr = res;

        while (head != null) {

            ListNode nn = head.next;

            //每次循环进来都把curr置为链表头，最开始的那个
            curr = res;

            //因为目前res的这个链表是从小到大排列的
            //这个循环是找到head目前对应的val应该插入到res的哪个节点
            while (curr.next != null && curr.next.val <= head.val) {
                curr = curr.next;
            }

            //找到head应该插入res的哪个节点
            //在res中进行插入
            head.next = curr.next;
            curr.next = head;
            head = nn;
        }
        return res.next;
    }