题解 | #单链表的排序#
单链表的排序
https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08
/**分治思想+快慢指针找中点切割链表
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
#include <vector>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param head ListNode类 the head node
* @return ListNode类
*/
ListNode* sortInList(ListNode* head) {
if(head==nullptr||head->next==nullptr) return head;
//使用快慢指针找到中点
ListNode* slow=head,*fast=head->next;
//注意为next,为了后续找到中点的前一个节点
while(fast!=nullptr&&fast->next!=nullptr){
slow=slow->next;
fast=fast->next->next;
}
//分割为两个链表
ListNode* newlist=slow->next;
slow->next=nullptr;//slow为中点前一个节点
//将两个链表继续分割
ListNode* left=sortInList(head);
ListNode* right=sortInList(newlist);
ListNode* phead=new ListNode(-1);//哨兵节点
ListNode* res=phead;
//归并排序
while(left!=nullptr&&right!=nullptr){
if(left->val<right->val){
phead->next=left;
left=left->next;
}
else{
phead->next=right;
right=right->next;
}
phead=phead->next;
}
//判断左右链表是否为空
phead->next=left==nullptr?right:left;
return res->next;
}
};