148

148. Sort List (Medium)

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

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

 

Example 1:

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

Example 2:

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

Example 3:

Input: head = []
Output: []

 

Constraints:

• The number of nodes in the list is in the range [0, 5 * 104].
• -105 <= Node.val <= 105

Companies:
Facebook, Adobe, Yahoo, Bloomberg, ByteDance

Related Topics:
Linked List, Sort

Similar Questions:

• Merge Two Sorted Lists (Easy)
• Sort Colors (Medium)
• Insertion Sort List (Medium)

Solution 1. Merge Sort

// OJ: https://leetcode.com/problems/sort-list/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(logN)
class Solution {
    ListNode* splitList(ListNode *head) {
        ListNode dummy, *p = &dummy, *q = &dummy;
        dummy.next = head;
        while (q && q->next) {
            q = q->next->next;
            p = p->next;
        }
        auto next = p->next;
        p->next = NULL;
        return next;
    }
    ListNode *mergeList(ListNode *a, ListNode *b) {
        ListNode head, *tail = &head;
        while (a && b) {
            ListNode *node;
            if (a->val <= b->val) {
                node = a;
                a = a->next;
            } else {
                node = b;
                b = b->next;
            }
            tail->next = node;
            tail = node;
        }
        if (a) tail->next = a;
        if (b) tail->next = b;
        return head.next;
    }
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        auto b = splitList(head);
        return mergeList(sortList(head), sortList(b));
    }
};

Solution 2. Quick Sort

// OJ: https://leetcode.com/problems/sort-list/
// Author: github.com/lzl124631x
// Time: O(NlogN) on average, O(N^2) in the worst case
// Space: O(logN) on averge, O(N) in the worst case
class Solution {
private:
    void quickSort(ListNode *begin, ListNode *end = NULL) {
        if (begin == end || begin->next == end) return;
        auto p = partition(begin, end);
        quickSort(begin, p.first);
        quickSort(p.second, end);
    }
    pair<ListNode*, ListNode*> partition(ListNode *begin, ListNode *end) {
        int pivot = begin->val;
        ListNode *eqHead = begin, *eqTail = begin, *p = begin->next;
        while (p != end) {
            if (p->val <= pivot) {
                if (p->val < pivot) {
                    swap(eqHead->val, p->val);
                    eqHead = eqHead->next;
                }
                swap(p->val, eqTail->next->val);
                eqTail = eqTail->next;
            }
            p = p->next;
        }
        return {eqHead, eqTail->next};
    }
public:
    ListNode* sortList(ListNode* head) {
        quickSort(head);
        return head;
    }
};

Solution 3. Bottom-up Merge Sort

// OJ: https://leetcode.com/problems/sort-list/solution/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
    pair<ListNode*, ListNode*> mergeList(ListNode *a, ListNode *b) {
        ListNode head, *tail = &head;
        while (a || b) {
            ListNode *node;
            if (!b || (a && a->val <= b->val)) {
                node = a;
                a = a->next;
            } else {
                node = b;
                b = b->next;
            }
            tail->next = node;
            tail = node;
        }
        return {head.next, tail};
    }
    int getLength(ListNode *head) {
        int ans = 0;
        for (; head; head = head->next, ++ans);
        return ans;
    }
public:
    ListNode* sortList(ListNode* head) {
        ListNode dummy;
        dummy.next = head;
        int length = getLength(head);
        for (int len = 1; len < length; len *= 2) {
            auto p = dummy.next, prev = &dummy;
            while (p) {
                auto a = p;
                for (int i = 1; i < len && p->next; ++i) p = p->next;
                auto b = p->next;
                p->next = NULL;
                if (b == NULL) break;
                p = b;
                for (int i = 1; i < len && p->next; ++i) p = p->next;
                auto next = p->next;
                p->next = NULL;
                auto [h, t] = mergeList(a, b);
                prev->next = h;
                t->next = next;
                p = next;
                prev = t;
            }
        }
        return dummy.next;
    }
};