Sort a linked list using insertion sort.

Solution1：插入排序

思路：新建dummy->null将sort好的排到dummy 能够使得代码更简洁并减少插入到最前端的corner case

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

实现1a: 每次重置搜索指针prev至头为再搜索 prev = dummy
实现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;
    }
}