148 - Sort List

Problem

Given the head of a linked list, return the list after sorting it in ascending order.

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Constraints:

• The number of nodes is in the range [0, 5 * 10^4]
• -10^5 <= Node.val <= 10^5

Follow-up: sort in O(n log n) time and O(1) memory.

Approach

The obvious move is to dump the values into a vector, sort it, and rebuild. That is O(n log n) and it passes:

vector<int> vec;
for (ListNode* p = head; p; p = p->next) vec.push_back(p->val);
sort(vec.begin(), vec.end());
// rebuild

class Solution {
    ListNode* split(ListNode* head, int n) {
        while(--n && head) head = head->next;
        ListNode* rest = head ? head->next : nullptr;
        if(head) head->next = nullptr;
        return rest;
    }
    ListNode *merge(ListNode* l, ListNode* r, ListNode* tail) {
        ListNode* curr = tail;
        while(l && r) {
            if(l->val <= r->val) {
                curr->next = l;
                l = l->next;
            } else {
                curr->next = r;
                r = r->next;
            }
            curr = curr->next;
        }
        curr->next = l ? l : r;
        while(curr->next) curr = curr->next;
        return curr;
    }
public:
    ListNode* sortList(ListNode* head) {
        int n = 0;
        ListNode* curr = head;
        while(curr) {
            n++;
            curr = curr->next;
        }

        ListNode dummy(0, head);
        for(int i = 1; i < n; i *= 2) {
            ListNode* prev = &dummy;
            ListNode* curr = dummy.next;
            while(curr) {
                ListNode* l = curr;
                ListNode* r = split(l, i);
                curr = split(r, i);
                prev = merge(l, r, prev);
            }
        }
        return dummy.next;
    }
};

• time: O(n log n) - log n passes, each merging every node once
• space: O(1) - a fixed set of pointers, no recursion, nodes relinked in place