# My O(n log n) time, O(1) space solution

• Nice problem. I use a non-recurisve way to write merge sort.
For example, the size of ListNode is 8,

Round #1 block_size = 1

(a1, a2), (a3, a4), (a5, a6), (a7, a8)

Compare a1 with a2, a3 with a4 ...

Round #2 block_size = 2

(a1, a2, a3, a4), (a5, a6, a7, a8)

merge two sorted arrays (a1, a2) and (a3, a4), then merge tow sorted arrays(a5, a6) and (a7, a8)

Round #3 block_size = 4

(a1, a2, a3, a4, a5, a6, a7, a8)

merge two sorted arrays (a1, a2, a3, a4), and (a5, a6, a7, a8)

No need for round #4 cause block_size = 8 >= n = 8

``````class Solution {
public:
int count_size(ListNode *node){
int n = 0;
while (node != NULL){
node = node->next;
++n;
}
return n;
}
int block_size = 1, n = count_size(head), iter = 0, i = 0, a = 0, b = 0;
ListNode *last = NULL, *it = NULL, *A = NULL, *B = NULL, *tmp = NULL;
while (block_size < n){
iter = 0;
while (iter <  n){
a = min(n - iter, block_size);
b = min(n - iter - a, block_size);

A = it;
if (b != 0){
for (i = 0; i < a - 1; ++i) it = it->next;
B = it->next;
it->next = NULL;
it = B;

for (i = 0; i < b - 1; ++i) it = it->next;
tmp = it->next;
it->next = NULL;
it = tmp;
}

while (A || B){
if (B == NULL || (A != NULL && A->val <= B->val)){
last->next = A;
last = last->next;
A = A->next;
} else {
last->next = B;
last = last->next;
B = B->next;
}
}
last->next = NULL;
iter += a + b;
}
block_size <<= 1;
}
}
};``````

• can you give a explanation of your below code:
what's a b here for?
a = min(n - iter, block_size);
b = min(n - iter - a, block_size);

``````            if (b != 0){ //what's the mean, if b != 0
for (i = 0; i < a - 1; ++i) it = it->next;
B = it->next;
it->next = NULL;
it = B;

for (i = 0; i < b - 1; ++i) it = it->next;
tmp = it->next;
it->next = NULL;
it = tmp;
}

while (A || B){ //also here??
if (B == NULL || (A != NULL && A->val <= B->val)){
last->next = A;
last = last->next;
A = A->next;
} else {
last->next = B;
last = last->next;
B = B->next;
}
}
last->next = NULL;
iter += a + b;``````

• When merge two sorted lists, the lengths of two lists are a and b. when b != 0 we need to find the begin of the next two lists to be sorted. A||B means that we still need to merge them while list A or list B is not NULL. If A == NULL ,the list A has already added to the new list.

• but, what the mean of iter, i saw every loop the iter will add a+b. and what's your method to calculate a and b?
a = min(n - iter, block_size);
b = min(n - iter - a, block_size);

• a and b suppose to be blocksize, but it may do not have enough numbers to do. for example n = 10, blocksize = 4. first a = 4, b = 4, then iter = 8. next round, a should be 4, but only remain n - iter = 2 numbers. Therefore a = 2. Use the same way to calculate b.

• comment retracted . neat solution ...

• Very nice solution. I think this line is unnecessary:

last->next = NULL;

• Good idea!!!

• Wow, it is really a clever solution!

• Great Idea!!!

• I can't understand your code.

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