I've implemented quick sort at first, but it failed in the worst scenario and got a TLE. I guess that means it reaches the O(n^2).

Then I checked the cheat sheet and implemented merged sort, it passed like a charm.

I've also checked heap sort, it works best with an array, but in this case it's linked list here, so the space complexity will definitely not be O(1).

So, any better solution?

Code here:

```
ListNode *quickSort(ListNode *head, ListNode *fin) {
if (head == fin) {
return head;
}
ListNode *left = head;
ListNode *right = head;
ListNode *next = NULL;
ListNode *cur = NULL;
for (cur = head->next; cur != fin; cur = next) {
next = cur->next;
if (cur->val < head->val) {
cur->next = left;
left = cur;
}
else {
right->next = cur;
right = cur;
}
}
/* right->next = fin; */
head->next = quickSort(head->next, fin);
return quickSort(left, head);;
}
ListNode *sortList(ListNode *head) {
return quickSort(head, NULL);
}
```