My method is similar to quicksort, and its space complexity is not strictly const. But I think the time complexity is O(nlogn), why still gets a TLE?

```
class Solution {
public:
ListNode *sortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
if (head == NULL || head->next == NULL)
return head;
pair<ListNode*, ListNode*> ret = partition(head, NULL);
return ret.first;
}
pair<ListNode*, ListNode*> partition(ListNode *begin, ListNode *end) {
// return the first and last point of the sorted range [begin, end)
if (begin == NULL || begin->next == end)
return make_pair(begin, begin);
ListNode *p1 = new ListNode(0);
ListNode *first_part = p1;
ListNode *p2 = new ListNode(0);
ListNode *second_part = p2;
int base_val = begin->val;
ListNode *cur = begin->next;
// partition: first_part is the element less than base_val, second_part is the other
while (cur != end) {
if (cur->val < base_val) {
first_part->next = cur;
first_part = cur;
} else {
second_part->next = cur;
second_part = cur;
}
cur = cur->next;
}
first_part->next = NULL;
second_part->next = NULL;
pair<ListNode*, ListNode*> first_pair = partition(p1->next, NULL);
pair<ListNode*, ListNode*> second_pair = partition(p2->next, NULL);
delete p1;
delete p2;
ListNode *new_head = first_pair.first;
// concatenate
if (new_head == NULL) {
new_head = begin;
} else {
first_pair.second->next = begin;
}
begin->next = second_pair.first;
if (second_pair.second != NULL)
return make_pair(new_head, second_pair.second);
else
return make_pair(new_head, begin);
}
};
```