struct ListNode {

};

ListNode* cut(ListNode* head, int size){

auto p = head;

while(--size && p!=nullptr){

p = p->next;

}

if(!p)

return nullptr;

auto q = p->next;

p->next = nullptr;

return q;

}

ListNode* merge(ListNode* first, ListNode* second){

ListNode Head(0);

auto p = &Head;

while(first && second){

if(first->val < second->val){

p->next = first;

p = first;

first = first->next;

}

else{

p->next = second;

p = second;

second = second->next;

}

}

if(first)

p->next = first;

if(second)

p->next = second;

return Head.next;

}

ListNode* sortList(ListNode* head) {

ListNode dummyHead(0);

dummyHead.next = head;

int length = 0;

auto p = head;

while(p){

++ length;

p = p->next;

}

for(int size = 1; size < length; size <<=1){

auto cur = dummyHead.next;

auto trail = &dummyHead;

while(cur){

auto first = cur;

auto second = cut(cur,size);

cur = cut(second,size);

trail->next = merge(first, second);

while(trail->next)

trail = trail->next;

}

}

return dummyHead.next;

}