### 题目

Sort a linked list using insertion sort.

### 指针遍历

list的头部维护一个排过序的子串，对list中的每个节点都遍历这个排过序的子串，然后插到合适的位置，保持这个子串有序。程序打印出来的过程如下：

Original List: 77->61->36->40->9->93->91->63->85->54
61 inserted before 77
Now List = 61->77->36->40->9->93->91->63->85->54
36 inserted before 61
Now List = 36->61->77->40->9->93->91->63->85->54
40 inserted before 61
Now List = 36->40->61->77->9->93->91->63->85->54
9 inserted before 36
Now List = 9->36->40->61->77->93->91->63->85->54
93 insert after 77
Now List = 9->36->40->61->77->93->91->63->85->54
91 inserted before 93
Now List = 9->36->40->61->77->91->93->63->85->54
63 inserted before 77
Now List = 9->36->40->61->63->77->91->93->85->54
85 inserted before 91
Now List = 9->36->40->61->63->77->85->91->93->54
54 inserted before 61
Now List = 9->36->40->54->61->63->77->85->91->93
Sorted List: 9->36->40->54->61->63->77->85->91->93


#### 代码

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
ListNode dummy = new ListNode(0); dummy.next = head; // 哨兵
outWhile:
while (cur != null) {
ListNode insertAfterIt = dummy; // 插入在它后面
while (insertAfterIt.next != cur) {
if (insertAfterIt.next.val >= cur.val) {
ListNode temp = cur;
pre.next = cur.next;
cur = cur.next;
temp.next = insertAfterIt.next;
insertAfterIt.next = temp;
continue outWhile;
}
insertAfterIt = insertAfterIt.next;
}
pre = cur;
cur = cur.next;
}
return dummy.next;
}
}