题解 | #单链表的排序#

归并排序

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
 
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;

        while(l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        if (l1)
            tail->next = l1;
        else
            tail->next = l2;

        return dummy.next;
    }
    ListNode* sortInList(ListNode* head) {
        
        if (!head || !head->next)
            return head;

        ListNode* slow = head, *fast = head, *prev = nullptr;

        while (fast && fast->next) {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }

        prev->next = nullptr;

        ListNode *left = sortInList(head);
        ListNode *right = sortInList(slow);

        return merge(left, right);

    }
};