Sort List

Desicription

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

Example 1:

1
2
Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

1
2
Input: -1->5->3->4->0
Output: -1->0->3->4->5

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
vector<int> vec;
for(auto it = head; it != NULL; it = it->next)
vec.push_back(it->val);
sort(vec.begin(), vec.end());
int index = 0;
for(auto it = head; it != NULL; it = it->next)
it->val = vec[index++];
return head;
}
};