Sort List

Sort List

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

Solutions

🧠 Cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    //count sort with a lot of SPACE
    //but O(1) space and O(n) time
    ListNode* sortList(ListNode* head)
    {
        vector<size_t> minus_cout_table(100000);
        vector<size_t> plus_cout_table(100000);

        for(auto iter = head; iter; iter = iter->next)
        {
            if(iter->val < 0)
                minus_cout_table[abs(iter->val)]++;
            else
                plus_cout_table[iter->val]++;
        }

        ListNode *new_head = nullptr,
        *iter = nullptr;

        for(int i = minus_cout_table.size()-1; i >= 0; i--)
        {
            if(minus_cout_table[i])
            for(int j = 0; j < minus_cout_table[i]; j++)
            {

                ListNode* new_node = new ListNode(-1*i);
                if(!iter)
                {
                    new_head = new_node;
                    iter = new_head;
                }
                else
                {
                    iter->next = new_node;
                    iter = new_node;
                }
            }
        }

        for(int i = 0; i <  plus_cout_table.size(); i++)
        {
            if(plus_cout_table[i])
            for(int j = 0; j < plus_cout_table[i]; j++)
            {

                ListNode* new_node = new ListNode(i);
                if(!iter)
                {
                    new_head = new_node;
                    iter = new_head;
                }
                else
                {
                    iter->next = new_node;
                    iter = new_node;
                }
            }
        }

        return new_head;
    }
};