147. 对链表进行插入排序
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5
思路
1 cur节点为要插入到有序链表的节点
2 首先将cur与有序链表中的尾结点比较，如果已排序尾结点小于等于要插入的节点，则要插入的节点已经在正确的位置，无需挪动。将尾结点向后移一个即可
3 否则，从头遍历有序链表，找到cur的位置，将其插入即可
代码
class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null){
return head;
}
ListNode sentinal = new ListNode(Integer.MIN_VALUE);
sentinal.next = head;
ListNode cur = head.next;
ListNode p1;
ListNode p2;
ListNode newTail = head;
while (cur != null){
p1 = sentinal;
p2 = sentinal.next;
//先比较要插入的节点和已排序的链表中尾结点。
// 如果已排序尾结点小于等于要插入的节点，则要插入的节点已经在正确的位置，无需挪动。
// 将尾结点向后移一个即可
if (newTail.val <= cur.val){
newTail = cur;
cur = cur.next;
continue;
}
while (cur.val >= p2.val){
p1 = p1.next;
p2 = p2.next;
}
newTail.next = cur.next;
cur.next = p2;
p1.next = cur;
cur = newTail.next;
}
return sentinal.next;
}
}