Sort a linked list using insertion sort.

Solution1：插入排序

思路：新建dummy->null將sort好的排到dummy 能夠使得代碼更簡潔并減少插入到最前端的corner case

屏幕快照 2017-09-12 下午2.10.35.png

實現(xiàn)1a: 每次重置搜索指針prev至頭為再搜索 prev = dummy
實現(xiàn)1b: 只有當新結點值小于等于prev才重置prev至頭為再搜索(otherwise可以直接append)，所以改為if (cur.val < prev.val) prev = dummy;

Time Complexity: O(N^2) Space Complexity: O(1)

Solution2：插入排序 Round1

Time Complexity: O(N^2) Space Complexity: O(1)

Solution1a Code：

class Solution {
    public ListNode insertionSortList(ListNode head) {
         ListNode dummy = new ListNode(0);
         ListNode prev = dummy;
         ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next; // save next

            while (prev.next != null && prev.next.val < cur.val) {
                prev = prev.next;
            }

            cur.next = prev.next;
            prev.next = cur;
            prev = dummy; // reset
            cur = next;
        }
        return dummy.next;
    }
}

Solution1b Code：

class Solution {
    public ListNode insertionSortList(ListNode head) {
         ListNode dummy = new ListNode(0);
         ListNode prev = dummy;
         ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next; // save next

            /* Before insert, the prev is at the last node of the sorted list.
               Only the last node's value is larger than the current inserting node 
               should we move the temp back to the head*/
            if (cur.val < prev.val) prev = dummy;

            while (prev.next != null && prev.next.val < cur.val) {
                prev = prev.next;
            }

            cur.next = prev.next;
            prev.next = cur;
            // prev = dummy; // Don't set prev to the head of the list after insert
            cur = next;
        }
        return dummy.next;
    }
}

Solution2 Round1 Code：

class Solution {
    public ListNode insertionSortList(ListNode head) {
        
        ListNode dummy = new ListNode(0);
        
        ListNode src = head;
        while(src != null) {
            ListNode src_next = src.next;
            
            // find insert pos
            ListNode prev_cur = dummy;
            ListNode cur = dummy.next;
            while(cur != null && cur.val < src.val) {
                prev_cur = cur;
                cur = cur.next;
            }
            
            // insert 
            src.next = prev_cur.next;
            prev_cur.next = src;

            src = src_next;
        }
        return dummy.next;
    }
}