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;
}
}
