链表排序

目录

插入排序

LeetCode147 对链表进行插入排序

归并排序

LeetCode148 排序链表

---

插入排序

LeetCode147 对链表进行插入排序

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* insertionSortList(ListNode* head) {if(head==nullptr) return head;if(head->next==nullptr) return head;ListNode* first=new ListNode(0);first->next=head;ListNode* pre=head;ListNode* cur=head->next;while(cur){if(cur->val<pre->val){//当前节点小于最后一个已排序节点ListNode* p=first;while(cur->val>p->next->val) p=p->next;pre->next=cur->next;//保存cur->nextcur->next=p->next;p->next=cur;//在p之后插入curcur=pre->next;//下一个待排序节点//此时不用改变pre指向！因为pre没有变，只是待排序元素变了位置}else{//当前节点大于等于最后一个已排序节点，则不需要插入pre=pre->next;cur=cur->next;}}return first->next;//不能返回head，head仍然指向原链表的第一个节点}
};

 时间复杂度：O(n^2)

空间复杂度：O(1)

归并排序

LeetCode148 排序链表

（1）找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。

（2）对两个子链表分别排序。

（3）将两个排序后的子链表合并，得到完整的排序后的链表。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* sortList(ListNode* head) {return sortL(head,nullptr);}ListNode* sortL(ListNode* head,ListNode* tail){if(head==nullptr) return nullptr;if(head->next==tail){ //如果链表只有一个节点head->next=nullptr; //将该节点的 next 置为 nullptr，表示这个子链表结束return head;}ListNode* fast=head;ListNode* slow=head;//使用快慢指针法找到链表的中间点，slow 是中间点，fast 是快指针while(fast!=tail){fast=fast->next;slow=slow->next;if(fast!=tail){ //确保fast不越界fast=fast->next;}}ListNode* mid=slow; //slow 指向链表的中间节点，作为分割点//对链表的左半部分和右半部分分别进行递归排序，然后合并return merge(sortL(head,mid),sortL(mid,tail));}ListNode* merge(ListNode* head1,ListNode* head2){ListNode* L=new ListNode(0);L->next=nullptr;ListNode* r1=head1;ListNode* r2=head2;ListNode* cur=L;while(r1&&r2){if(r1->val<r2->val){cur->next=r1;r1=r1->next;}else{cur->next=r2;r2=r2->next;}cur=cur->next;}if(r1!=nullptr) cur->next=r1;if(r2!=nullptr) cur->next=r2;return L->next;}
};

 时间复杂度：O(n log n)

空间复杂度：O(log n)