Insertion Sort List

刚开始想的复杂很多，后来重新思考了一遍，发现是我想太复杂了。

这个是重改后的第一版，发现效率还能继续提升：

if(head==NULL || head->next==NULL) return head;
ListNode* nh=head;
head = head->next;
nh->next = NULL;
while(head!=NULL) {
if(head->val < nh->val) {
ListNode *a = head->next;
head->next = nh;
nh = head;
head = a;
}
else {
if(nh->next == NULL) {
nh->next = head;
head = head->next;
nh->next->next = NULL;
continue;
}
ListNode *p = nh;
while(p->next && head->val > p->next->val) {
p = p->next;
}
if(p->next) {
ListNode *a = head->next;
head->next = p->next;
p->next = head;
head = a;
}
else {
p->next = head;
head = head->next;
p->next->next = NULL;
}
}
}
return nh;

当插入结点head一直大于当前结点p的时候，p可以不归位，这样节省了很多效率，改进后代码如下：

ListNode* insertionSortList(ListNode* head) {
if(head==NULL || head->next==NULL) return head;
ListNode *nh=head, *p=nh;
head = head->next;
nh->next = NULL;
while(head!=NULL) {
if(head->val < nh->val) {
ListNode *a = head->next;
head->next = nh;
nh = head;
head = a;
}
else {
if(p->val > head->val) {
p = nh;
}
while(p->next && head->val > p->next->val) {
p = p->next;
}
if(p->next) {
ListNode *a = head->next;
head->next = p->next;
p->next = head;
head = a;
}
else {
p->next = head;
head = head->next;
p->next->next = NULL;
}
}
}
return nh;
}

效率对比：改进前测试速度为80ms，改进后测试速度为24ms，节省了70%的时间！

Insertion Sort List

原文：http://www.cnblogs.com/xdlyy/p/5410979.html