Sort a linked list using insertion sort.
问题：实现单向链表的插入排序。
这是比较常规的一个算法题目。 从左往右扫列表，每次将指针的下一个元素插入前面已排好序的对应位置中。
需要注意的一定是，列表只能定位下一个元素，不能定位前一个元素，所有，每次插入位置的适合，都是对左右指针的下一个元素进行操作。
void insertSort(ListNode* p1, ListNode* p2){
ListNode* next2 = p2->next;
p2->next = p2->next->next;
next2->next = p1->next;
p1->next = next2;
}
ListNode* insertionSortList(ListNode* head) {
if (head == NULL){
return head;
}
ListNode* r = head;
while(r->next != NULL){
ListNode* l = new ListNode();
l->next = head;
while(l != r){
if (l->next->val > r->next->val){
if (l->next == head) {
head = r->next;
}
insertSort(l, r);
break;
}
l = l->next;
}
if (r->next != NULL && r->next->val >= r->val) {
r = r->next;
}
}
return head;
}