Sort a linked list using insertion sort.
一刷
题解：没有很好的办法，只能每次从头找。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode insertionSortList(ListNode head) {
if(head == null) return head;
ListNode helper = new ListNode(0);
ListNode cur = head; //the node will be inserted
ListNode pre = helper; //insert node between pre and pre.next
ListNode next = null;//the next node will be inserted
while(cur!=null){
next = cur.next;
while(pre.next!=null && pre.next.val<cur.val) pre = pre.next;
//insert between pre and per.next
cur.next = pre.next;
pre.next = cur;
pre = helper;
cur = next;
}
return helper.next;
}
}
