148 Sort List

Sort a linked list in O(n log n) time using constant space complexity.

The Idea:

• Just like regular merge sort, except we have to iterate to the half-way point in the list.

• Prev is required, as it always follows that iterslow = prev->next;

    ListNode* sortList(ListNode* head)
    {
        // a list of size 0 or 1 is sorted.
        if (!head || !(head->next))
            return head;

        ListNode *prev = nullptr;
        ListNode *iter_fast = head;
        ListNode *iter_slow = head;

        // split into two halves:
        // half1 : head to prev
        // half2 : iter_slow to end
        while (iter_fast && iter_fast->next) {
            prev = iter_slow;
            iter_slow = iter_slow->next;
            iter_fast = iter_fast->next->next;
        }
        prev->next = nullptr;

        ListNode *l1 = sortList(head);
        ListNode *l2 = sortList(iter_slow);

        return merge(l1, l2);
    }


    ListNode* merge(ListNode *head, ListNode *slow)
    {
        ListNode *newHead = nullptr;

        // set up the front of the list
        if (head->val < slow->val) {
            newHead = head;
            head = head->next;
        }
        else {
            newHead = slow;
            slow = slow->next;
        }

        ListNode *newHead_itr = newHead;

        // iterate through the end of the shortest list
        while (head && slow) {
            if (head->val < slow->val) {
                newHead_itr->next = head;
                head = head->next;
            }
            else {
                newHead_itr->next = slow;
                slow = slow->next;
            }
            newHead_itr = newHead_itr->next;
        }

        // append the larger list if it exists
        if (slow) newHead_itr->next = slow;
        else if (head) newHead_itr->next = head;

        return newHead;
    }