```
class Solution {
public:
ListNode *sortList(ListNode *head) {
if(!head || !head -> next) return head;
ListNode * cur = head;
int len = 0;
while (cur) len++, cur = cur -> next;
ListNode * ans = new ListNode(0);
ans -> next = head;
for (int width = 1; width < len; width += width){
ListNode * start1, *end1, *start2, *end2, *last;
last = ans;
while (last -> next) {
start1 = last -> next;
end1 = move(width, start1);
if(end1) start2 = end1;
else
break;
end2 = move(width, start2);
ListNode * next_for_last = end2 ;
ListNode * new_last;
last -> next = mergeSort(start1, end1, start2, end2, new_last);
last = new_last;
last -> next = next_for_last;
}
}
return ans -> next;
}
private:
ListNode * move (int k, ListNode * cur) {
for (int i = 0; i < k && cur; i++) cur = cur -> next;
return cur;
}
ListNode * mergeSort (ListNode * start1, ListNode * end1, ListNode * start2, ListNode * end2, ListNode * &new_last) {
if (!start1) return start2;
if (!start2) return start1;
ListNode * merge , *head;
if (start1 -> val < start2 -> val) {
merge = start1;
start1 = start1 -> next;
} else {
merge = start2;
start2 = start2 -> next;
}
head = merge;
while (start1 != end1 && start2 != end2) {
if (start1->val < start2->val) {
merge -> next = start1;
start1 = start1 -> next;
} else {
merge -> next = start2;
start2 = start2 -> next;
}
merge = merge -> next;
}
while (start1 != end1) {
merge -> next = start1;
start1 = start1 -> next;
merge = merge -> next;
}
while (start2 != end2) {
merge -> next = start2;
start2 = start2 -> next;
merge = merge -> next;
}
new_last = merge;
return head;
}
};
```