```
class Solution {
public:
ListNode* sortList(ListNode* head) {
// corner check if head is NULL or there is only one node, sorting is not neccessary.
if (!head || !head->next) {
return head;
}
// preparation for merge sort finding the mid of the list
ListNode* mid = findMid(head);
// seperate one list to two
ListNode* right = mid->next;
// add NULL to the first half list
mid->next = NULL;
// recursively sort two lists
head = sortList(head);
right = sortList(right);
// merge two lists
return mergeList(head, right);
}
private:
ListNode* mergeList(ListNode* left, ListNode* right) {
if (!left){
return right;
}
if (!right) {
return left;
}
// define a dummy node to link all the nodes from two lists in ascending order.
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while (left && right) {
if (left->val < right->val) {
cur->next = left;
left = left->next;
} else {
cur->next = right;
right = right->next;
}
cur = cur->next;
}
while (left) {
cur->next = left;
left = left->next;
cur = cur->next;
}
while (right) {
cur->next = right;
right = right->next;
cur = cur->next;
}
return dummy->next;
}
// helper fuction use two pointers to find the left mid of the list.
ListNode* findMid(ListNode* list) {
if (!list) {
return list;
}
ListNode* walker = list;
ListNode* runner = list->next;
while (runner && runner->next) {
walker = walker->next;
runner = runner->next->next;
}
return walker;
}
};
```

Time complexity is **O(nlogn)**, n is the number of nodes on the linked list

Space complexity is **O(1)**