> For the complete documentation index, see [llms.txt](https://anton-veselskyi.gitbook.io/codding-problems-solutions/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://anton-veselskyi.gitbook.io/codding-problems-solutions/leetcode/medium/sort-list.md).

# Sort List

## [Sort List](https://leetcode.com/problems/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:** ![](https://assets.leetcode.com/uploads/2020/09/14/sort_list_1.jpg)

```

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

**Example 2:** ![](https://assets.leetcode.com/uploads/2020/09/14/sort_list_2.jpg)

```

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

```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;
    }
};
```