链表的归并排序

文章目录

• • • 代码：

---

代码：

class Solution {
public:
    ListNode*sortList(ListNode*head){
        if(head==nullptr||head->next==nullptr)  return head;
        ListNode*head1=head;
        ListNode*head2=split(head);//一条链表分成两段分别递归排序
        head1=sortList(head1);
        head2=sortlist(head2);
        return merge(head1,head2);//二叉树后序遍历思想，先递归排序左右然后合并返回
    }
    //双指针找单链表中点模板
    ListNode*split(ListNode*head){
        ListNode*slow=head,*fast=head->next;
        while(fast!=nullptr&&fast->next!=nullptr){
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode*mid=slow->next;
        slow->next=nullptr;
        return mid;
    }
    //合并两个排序链表模板
    ListNode*merge(ListNode*head1,ListNode*head2){
        ListNode*dummy=new ListNode(0),*p=dummy;
        while(head1!=nullptr&&head2!=nullptr){
            if(head1->val<head2->val){
                p=p->next=head1;
                head1=head1->next;//单链表的赋值
            }
            else
            {
                p=p->next=head2;
                head2=head2->next;
            }
        }
        if(head1!=nullptr) p->next=head1;
        if(head2!=nullptr) p->next=head2;
        return dummy->next;
    }

};)