Sort a linked list using insertion sort.
链表的插入排序。
需要创建一个虚拟节点。注意点就是不要节点之间断了。
class Solution {
public: ListNode* insertionSortList(ListNode* head) {
if(head==NULL||head->next==NULL)
return head;
ListNode* newhead = new ListNode(-);
newhead->next=head;
ListNode* q=head;
ListNode* p=head->next;
while(p!=NULL){
ListNode* s1=newhead;
ListNode* s2=s1->next;
while(s2!=p&&s2->val<=p->val){
s1=s2;
s2=s2->next;
}
if(s2!=p){
s1->next=p;
q->next=p->next;
p->next=s2; p=q->next;}
else{
q=p;
p=p->next;
}
}
return newhead->next;
}
};