https://leetcode.com/problems/sort-list/
對于整數(shù)構(gòu)成的鏈表吱殉，將其排序 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) {

        //結(jié)果鏈表
        ListNode res = new ListNode(-1);

        ListNode curr = res;

        while (head != null) {

            ListNode nn = head.next;

            //每次循環(huán)進來都把curr置為鏈表頭栅受，最開始的那個
            curr = res;

            //因為目前res的這個鏈表是從小到大排列的
            //這個循環(huán)是找到head目前對應的val應該插入到res的哪個節(jié)點
            while (curr.next != null && curr.next.val <= head.val) {
                curr = curr.next;
            }

            //找到head應該插入res的哪個節(jié)點
            //在res中進行插入
            head.next = curr.next;
            curr.next = head;
            head = nn;
        }
        return res.next;
    }