# A different non-recursive solution using a stack of O(log n) space

• I am not trying to spit the list into two equal halves. I use a stack to store the heads of lists of 2^i sizes. My algorithm works as this:

1. Loop through all element.
1. Make it as a length 1 list, named q.
2. Keep merging q with the top of stack as long as they have the same size.
3. Push q to stack.
2. Merge everything left in the stack.

The algorithm can be proved also runs in O(n log n) time.
Can you prove it? :))

``````class Solution {
public:

stack<pair<ListNode *, int> > s;
int len=0;

while (p) {
q=p;
len=1;
p=p->next;
q->next=0;

while( !s.empty() && s.top().second==len ) {
ListNode * tmp = s.top().first;
int tmplen=s.top().second;
s.pop();

q = mergeList(tmp,q);
len +=tmplen;
}
s.push(make_pair(q,len));
}

q = s.top().first;
len=s.top().second;
s.pop();

while(!s.empty()) {

ListNode * tmp = s.top().first;
int tmplen=s.top().second;
s.pop();

q = mergeList(tmp,q);
len +=tmplen;
}

return q;
}

ListNode *mergeList(ListNode *h1, ListNode* h2)
{
ListNode *p1 = h1, *p2 = h2;

ListNode *h = 0, *t = 0;
while (p1 || p2) {
if (p1 && p2) {
if (p1->val <= p2->val){
if (h) t = t->next = p1;
else t = h = p1;
p1 = p1->next;
}
else {
if (h) t = t->next = p2;
else t = h = p2;
p2 = p2->next;
}
}
else if (p1) {
if (h) t = t->next = p1;
else t = h = p1;
p1 = p1->next;
}
else {
if (h) t = t->next = p2;
else t = h = p2;
p2 = p2->next;
}
}
if (t) t->next = 0;
return h;
}
};``````

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