c++ merge sort, should be O(nlog(n)), O(1)


  • 0
    Z
    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            if (!head || !head->next) return head;
            ListNode *fast = head->next, *slow = head;
            while (fast && fast->next) {
                slow = slow->next;
                fast = fast->next->next;
            }
            ListNode *tail = slow->next;
            slow->next = NULL;
            head = sortList(head);
            tail = sortList(tail);
            ListNode *res, *p;
            if (head->val < tail->val) {
                p = res = head;
                head = head->next;
            } else {
                p = res = tail;
                tail = tail->next;
            }
            while (head && tail) {
                if (head->val < tail->val) {
                    p->next = head;
                    head = head->next;
                } else {
                    p->next = tail;
                    tail = tail->next;
                }
                p = p->next;
            }
            while (head) {
                p->next = head;
                head = head->next;
                p = p->next;
            }
            while (tail) {
                p->next = tail;
                tail = tail->next;
                p = p->next;
            }
            p->next = NULL;
            return res;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.