单链表排序

快排：

class Solution {public: ListNode* solve(ListNode* head, ListNode* pend){ if(head==NULL||head->next==pend) return head; int val = head->val; ListNode* p = head; ListNode* q = p->next; while(q!=pend){ if(q->val < val){ p = p->next; swap(p->val, q->val); } q = q->next; } swap(head->val, p->val); return p; } void quick_sort(ListNode* head, ListNode* pend){ if(head==pend) return; ListNode* p = solve(head, pend);//找出枢轴 quick_sort(head, p); quick_sort(p->next, pend); } ListNode* sortInList(ListNode* head) { // write code here quick_sort(head, NULL); return head; }};

利用vector和sort进行排序

class Solution {public: ListNode* sortInList(ListNode* head) { vector vec; ListNode* cur = head; // 1.构建vector while(cur) { vec.push_back(cur->val); cur = cur->next; } // 2.vector排序 sort(vec.begin(), vec.end()); // 3.构建链表 ListNode* dummy = new ListNode(0); ListNode* res = new ListNode(0); dummy->next = res; for(int i : vec) { res->next = new ListNode(i); res = res->next; } res->next = nullptr; return dummy->next->next; }};