147. Insertion Sort List

Sort a linked list using insertion sort.

这道题看的答案，一开始答案都看得有一些confusing. 然后自己在纸上画画过程才明白。
这里需要new一个dummy node, 因为现在的头节点head不一定是val最小的节点，有可能被移到后面去，所以head会动不能拿来当返回节点，所以需要一个dummy. 同时需要一个prev来确定插入的位置，然后用curt来遍历整个链表。先存下 temp = curt.next用于curt的后移；然后prev每次遍历必须reset回到头节点dummy, 这样才能将curt.val与sortedList里面的每一个节点的val来比较。如果prev有next节点，并且next.val <= curt.val,说明curt.val比当前prev节点要大，那么就可以继续看后面的节点，prev = prev.next;如果说不满足prev.next.val <= curt.val,说明我们找到了一个可以插入的位置，说明curt.val比现在prev.next.val小，我们正好把curt插到prev和prev.next之间。插入的过程代码很简单，只需要curt.next = prev.next; prev.next = curt；就可以，然后再后移curt到temp,继续遍历原链表。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null){
            return  head;
        }
        ListNode dummy = new ListNode(0);
        //move node prev to detemine where to insert 
        ListNode prev = dummy;
        ListNode curt = head;
        while (curt != null){
            //record curt.next node, or we'll lose its connection with the list
            ListNode temp = curt.next;
            //everytime we start from the very front of the list to determine where to insert
            prev = dummy;
            while (prev.next != null && prev.next.val <= curt.val){
                prev = prev.next;
            }
            //found the right position, add node curt after node prev.
            curt.next = prev.next;
            prev.next = curt;
            //move node curt to it's next(we recorded as temp)
            curt = temp;
        }
        //can't return head, head could be moved thus not continuing being the first item of the linkedlist
        return dummy.next;
    }
}