题解 | #单链表的排序#

题目

题解：使用归并法，利用快慢指针找到链表中点进行归并

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode *mergeSort(ListNode* head)
    {
        if(!head->next)return head;
        ListNode *fast=head->next,*slow=head;//快慢指针
        while(fast && fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode *tmp=slow->next;//tmp为右边一半
        slow->next=nullptr;//切割成两半
        ListNode *l=mergeSort(head);//左边一半
        ListNode *r=mergeSort(tmp);//右边一半
        ListNode *res=new ListNode(0),*pre=res;
        while(l && r)//合并两个有序链表
        {
            if(l->val<=r->val)
            {
                pre->next=l;
                l=l->next;
                pre=pre->next;
            }
            else
            {
                pre->next=r;
                r=r->next;
                pre=pre->next;
            }
        }
        pre->next=l?l:r;
        return res->next;
    }
    ListNode* sortInList(ListNode* head) {
        // write code here
        return mergeSort(head);
    }
};