对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
我的解法：在原始链表上维护一个已排序链表sort，sort的头节点p和尾节点q在初始时都指向head，h为未排序待处理的节点，每次取sort之后的第一个节点为h。为了减少算法的搜索次数，首先判断h所指节点的值是否小于sort的头节点p，若小于，则直接将h插入到链表头部；然后判断h所指节点的值是否大于sort的尾节点q，若大于，则直接将q和h后移一位；最后，若h的大小介于p和q之间，则遍历sort，找到h合适的插入位置并插入。
时间复杂度：O(n2)，空间复杂度：O(1)
class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode p = head, q = head, h = head.next;
while (h != null) {
p = head;
/*h所指节点小于已排序链表的头节点*/
if (p.val >= h.val) {
q.next = h.next;
h.next = p;
p = h;
head = p;
h = q.next;
} else if (q.val <= h.val) {
/*h所指节点大于已排序链表的尾节点*/
q = h;
h = h.next;
} else {
/*h所指节点的大小介于头节点和尾节点之间*/
while (p.val != q.val) {
/*找到合适的位置，将h所指的节点插入*/
if (p.next.val > h.val) {
break;
}
p = p.next;
}
q.next = h.next;
h.next = p.next;
p.next = h;
h = q.next;
}
}
return head;
}
}
