# My accepted solution using bottom-up merge sort in C++

• ``````class Solution {

public:

int len = 0;
while (cur) len++, cur = cur -> next;

ListNode * ans = new ListNode(0);

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;

if (start1 -> val < start2 -> val) {
merge = start1;
start1 = start1 -> next;
} else {
merge = start2;
start2 = start2 -> next;
}

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;
}

};``````

• elegant！with O(1) memory complexity

• The bottom up idea is good and can be used to achieve O(1) memory.

But I don't think your code uses O(1) memory.

To achieve O(1), you have to avoid creating new variables or calling other methods inside the loops.

• For example inside this loop variables are created only once, compiler creates them at the begining of this metod
for (int width = 1; width < len; width += width)

• I think you are right. I forgot that the memory is reused so no extra memory is needed.

• This post is deleted!

• It is not possible to have start1 null while start2 not null right?

• It is not possible, because I have this if
{{{ if(end1) start2 = end1;
else
break; }}}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.