```
class Solution {
public:
ListNode* halfSort(ListNode* start, ListNode* end)
{
if(start == NULL || start == end || start->next == end)
{
return start;
}
ListNode* target = start;
ListNode* curser = target;
while(curser->next != end)
{
if(curser->next->val< target->val)
{
ListNode* temp = curser->next;
curser->next = temp->next;
temp->next = start;
start = temp;
}
else
{
curser = curser->next;
}
}
start = halfSort(start, target);
while(target->next != end && target->next->val == target->val)
{
target=target->next;
}
target->next = halfSort(target->next, end);
return start;
}
ListNode* sortList(ListNode* head) {
return halfSort(head, NULL);
}
};
```