```
class Solution {
public:
ListNode *mergeSort(ListNode *head, int len) {
// if only less than two nodes left
if (len < 2) {
return head;
}
// divide it into two parts
ListNode *leftHead = head, *rightHead = head;
int leftLen = len >> 1;
int rightLen = len - leftLen;
for (int i = 0; i < leftLen; ++i) {
rightHead = rightHead->next;
}
// sort the left
leftHead = mergeSort(leftHead, leftLen);
// sort the right
rightHead = mergeSort(rightHead, rightLen);
// merge back
ListNode dummyNode(0);
head = &dummyNode;
while (leftLen > 0 && rightLen > 0) {
if (leftHead->val < rightHead->val) {
head->next = leftHead;
leftHead = leftHead->next;
--leftLen;
} else {
head->next = rightHead;
rightHead = rightHead->next;
--rightLen;
}
head = head->next;
}
head->next = leftLen > 0 ? leftHead : rightHead;
return dummyNode.next;
}
ListNode *sortList(ListNode *head) {
// get the list length
int listLen = 0;
ListNode *newHead = head;
while (newHead != NULL) {
++listLen;
newHead = newHead->next;
}
newHead = mergeSort(head, listLen);
return newHead;
}
};
```