1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| ListNode* insertionSortList(ListNode* head) {
ListNode*prehead=new ListNode(INT_MIN);
if(!head||!head->next)return head;
prehead->next=head;
ListNode*current=head->next;
ListNode*precur=head;
while(current)
{
if(current->val>=precur->val)
{
precur=current;
current=current->next;
}
else
{
int target=current->val;
precur->next=current->next;
ListNode*p=prehead;
ListNode*q=prehead->next;
while(q->val<target)
{
p=q;
q=q->next;
}
p->next=current;
current->next=q;
current=precur->next;
}
}
return prehead->next;
}
|