526互联

LeetCode 148. 排序链表

发布时间 2023-07-04 00:34:46作者: 穿过雾的阴霾
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head||!head->next)  return head;
        ListNode* fast=head,*slow=head;
        while(fast->next&&fast->next->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        fast=slow;
        slow=slow->next;
        fast->next=NULL;
        auto l=sortList(head);
        auto r=sortList(slow);
        return merge(l,r);
    }
    ListNode* merge(ListNode* l,ListNode* r)
    {
        ListNode* dummy=new ListNode(-1);
        ListNode* cur=dummy;
        while(l&&r)
        {
            if(l->val<r->val)
            {
                cur->next=l;
                l=l->next;
            }
            else
            {
                cur->next=r;
                r=r->next;
            }
            cur=cur->next;
        }
        cur->next=l?l:r;
        return dummy->next;
    }
};