果然脑袋混沌的时候就应该去放松一下,昨天下午实验室闷的一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; } else bk = 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; }