Insertion Sort List（自我感觉写的挺好）

本文主要是介绍Insertion Sort List（自我感觉写的挺好），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

果然脑袋混沌的时候就应该去放松一下，昨天下午实验室闷的一B，脑子蒙蒙的，一下午都在打这道题的酱油。没做对还很郁闷，今天早起随便写了一下，直接AC。

#include <iostream>
using namespace std;struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};class Solution {
public:ListNode *insertionSortList(ListNode *head) {if(!head || !head->next)return head;ListNode *lhs = new ListNode(0);lhs->next = head;ListNode *p = head->next;ListNode *bk = head;while(p){ListNode *q = lhs, *pnxt = p->next;while(q->next && p->val >= q->next->val && q->next != p){q = q->next;	}if(p->val < q->next->val){ListNode *t = q->next;q->next = p;bk->next = pnxt;p->next = t;	}elsebk = p;p = pnxt;}ListNode *re = lhs->next;delete lhs;return re;}ListNode* insert(ListNode *head, int val){ListNode *re = new ListNode(val);if(!head)return re;else{ListNode *p = head;while(p->next)p = p->next;p->next = re;}return head;}void print(ListNode *head){while(head){cout << head->val << endl;head = head->next;}}
};
int main(void)
{Solution s;ListNode *head = 0;for(int i = 9; i > 0; --i)head = s.insert(head, i);//s.print(head);head = s.insertionSortList(head);s.print(head);return 0;
}

这篇关于Insertion Sort List（自我感觉写的挺好）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---