Inspired by the SGI STL implementation of std::list::sort (which is also used in g++ and clang as well I believe). Keep an array to maintain list with different length. Every iteration grab one node from the remained list and merge it up the ladder.

```
class Solution {
public:
ListNode* sortList(ListNode* head) {
ListNode* ladder[14] = {nullptr, nullptr, nullptr, nullptr, nullptr,
nullptr, nullptr, nullptr, nullptr, nullptr,
nullptr, nullptr, nullptr, nullptr};
ListNode* current = nullptr;
int fill = 0;
while (head) {
current = head;
head = head->next;
current->next = nullptr;
int i = 0;
for (; i < fill && ladder[i]; ++i) {
current = merge(current, ladder[i]);
ladder[i] = nullptr;
}
ladder[i] = current;
if (i == fill) ++fill;
}
current = nullptr;
for (int i = 0; i < fill; ++i) {
current = merge(current, ladder[i]);
}
return current;
}
ListNode* merge(ListNode* a, ListNode* b) {
if (!a) return b;
ListNode dummy(0);
auto current = &dummy;
while (a && b) {
if (a->val < b->val) {
current->next = a;
a = a->next;
}
else {
current->next = b;
b = b->next;
}
current = current->next;
}
if (a) current->next = a;
if (b) current->next = b;
return dummy.next;
}
};
```