对链表进行插入排序。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
题解：
- 用[ pre, cur, post]遍历整个链表
- 取出cur，将pre与cur中间截断【因为无指针比较，如果pre直接与post连接，无法选择合适地点中止cur遍历，cur是不应该插入到post之后的】，cur与post中间截断
- 从链表头开始将每个结点与cur的值进行比较，找到cur的插入位置，分为前表(start 到 pre)尾(即pre之后，原位置，这种情况跳过即可)，或前表中间部分
- 将前表与后表进行连接
- 继续循环
class Solution { public ListNode insertionSortList(ListNode head) { if(head==null || head.next==null){ return head; } ListNode start = new ListNode(-1); start.next = head; //cur为当前待插入结点，pre为cur前结点 ListNode cur = head; ListNode pre = head; cur = pre.next; //post记录截断后带插入cur结点后续结点 ListNode post = null; while(pre!=null && cur!=null){ if(cur.val>=pre.val){ //cur当前有序 cur = cur.next; pre = pre.next; continue; } post = cur.next; pre.next = null; cur.next = null; ListNode tmp = start; while(tmp.next!=null && tmp.next.val<cur.val){ tmp = tmp.next; } //已找到位置，插入 cur.next = tmp.next; tmp.next = cur; //定位新pre并连接post pre.next = post; cur = pre.next; } return start.next; } }
