The idea is quite simple. use head to do 3 ways partition. Then sort the small part and the large part and merge.

```
class Solution {
public:
ListNode *sortList(ListNode *head) {
if(head == NULL || head->next == NULL){
return head;
}
int base = head->val;
ListNode *dummy_small = new ListNode(0);
ListNode *dummy_mid = new ListNode(0);
ListNode *dummy_large = new ListNode(0);
ListNode *pt[3]; // pt0 small, pt1 equal ,pt2 large
pt[0] = dummy_small;
pt[1] = dummy_mid;
pt[2] = dummy_large;
ListNode *p = head;
while(p != NULL){
int idx = 1;
if(p->val < base){
idx = 0;
}else if (p->val > base){
idx = 2;
}
pt[idx]->next = p;
p = p->next;
pt[idx] = pt[idx]->next;
pt[idx]->next = NULL;
}
ListNode* head_small = sortList(dummy_small->next);
ListNode* head_large = sortList(dummy_large->next);
// mid to large
pt[1]->next = head_large;
if(head_small == NULL){
return dummy_mid->next;
}else{
p = head_small;
while(p->next != NULL){
p = p->next;
}
p->next = dummy_mid->next;
return head_small;
}
}
};
```