题目

sort-list

算法

* 并归排序

代码

* 并归排序

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;
        fast = sortList(head);
        slow = sortList(slow);
        return merge(fast, slow);
    }

    ListNode *merge(ListNode *head1, ListNode *head2) {
        ListNode *res = new ListNode(-1);
        ListNode *cur = res;
        while (head1 && head2) {
            if (head1->val < head2->val) {
                cur->next = head1;
                head1 = head1->next;
            } else {
                cur->next = head2;
                head2 = head2->next;
            }
            cur = cur->next;
        }
        if (head1) cur->next = head1;
        if (head2) cur->next = head2;
        return res->next;
    }
};