题目
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3] 输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]
示例 3：
输入：head = [] 输出：[]
解题
方法一：利用数组排序
class Solution { public: ListNode* sortList(ListNode* head) { if(!head) return nullptr; //把链表节点加入到vector中 vector<ListNode*> arr; ListNode* cur=head; while(cur){ arr.push_back(cur); cur=cur->next; } //根据节点的值对vector排序 sort(arr.begin(),arr.end(),[](ListNode* a,ListNode* b){ return a->val<b->val; }); //将vector中的节点串起来即可 for(int i=0;i<arr.size();i++){ if(i==arr.size()-1) arr[i]->next=nullptr; else{ arr[i]->next=arr[i+1]; } } return arr[0]; } };
方法二：归并排序
class Solution { public: ListNode* sortList(ListNode* head) { if(!head||!head->next) return head; ListNode* slow=head; ListNode* fast=head; while(fast->next&&fast->next->next){ slow=slow->next; fast=fast->next->next; } // 切链 fast=slow->next; slow->next=nullptr; return merge(sortList(head),sortList(fast)); } ListNode* merge(ListNode* l1,ListNode* l2){ ListNode dummy; ListNode* cur=&dummy; while(l1&&l2){ if(l1->val<l2->val){ cur->next=l1; l1=l1->next; }else{ cur->next=l2; l2=l2->next; } cur=cur->next; } cur->next=l1?l1:l2; return dummy.next; } };
方法三：快排
#include<iostream> #include<climits> #include<vector> #include<algorithm> #include<numeric> #include <string> using namespace std; struct Node{ int val; Node* pre; Node* next; Node(int _val):val(_val),pre(nullptr),next(nullptr){} }; void pushNode(Node* tail,Node* p){ tail->next=p; p->pre=tail; } void quickSort(Node* head,Node* tail){ if(tail==nullptr||head==nullptr||head==tail) return; Node* p1=head; Node* p2=tail; while(p1!=p2){ while(p1!=p2&&p2->val>=head->val) p2=p2->pre; while(p1!=p2&&p1->val<=head->val) p1=p1->next; swap(p1->val,p2->val); } swap(p1->val,head->val); quickSort(head,p1->pre); quickSort(p1->next,tail); } int main(){ Node* head=new Node(1); Node* tail=head; Node* p2=new Node(3); pushNode(tail,p2); tail=tail->next; Node* p3=new Node(2); pushNode(tail,p3); tail=tail->next; quickSort(head,tail); for(Node* cur=head;cur;cur=cur->next){ cout<<cur->val<<endl; } system("pause"); return 0; }
