# Non recursive merge sort solution in C++,constant space complexity,python also AC

• C++ version:

``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
private:
void myMerge(ListNode *head, ListNode *p, ListNode *q)
{
while (p && q)
{
if (p->val < q->val)
{
p = p->next;
}
else
{
q = q->next;
}
}
}

public:
int n, i, j, k;
ListNode *dummy = new ListNode(0);
ListNode *pt = dummy;
ListNode *qt = dummy;
ListNode *pdummy = dummy;
ListNode *qdummy = dummy;
for (n = 1; p->next; n++)
p = p->next;
for (k = 1; k < n; k <<= 1)
{
pdummy = dummy;
qdummy = dummy->next;
while (qdummy)
{
p = qdummy;
pt = p;
for (i = 0; i < k; i++)
{
qt = pt;
pt = pt->next;
if (pt == NULL)
break;
}
if (pt == NULL)
{
pdummy->next = qdummy;
break;
}
qt->next = NULL;
q = pt;
for (i = 0; i < k; i++)
{
qt = pt;
pt = pt->next;
if (pt == NULL)
break;
}
qdummy = pt;
qt->next = NULL;

myMerge(pdummy, p, q);
if (qdummy)
{
for (i = 0; i < 2*k; i++)
pdummy = pdummy->next;
}
}
}
return dummy->next;
}
};
``````

================================================================

python version:

``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
# @return a ListNode
while p and q:
if p.val < q.val:
p = p.next;
else:
q = q.next;
if p:
if q:

return None
dummy = ListNode(0)
pt = dummy
qt = dummy
pdummy = dummy
qdummy = dummy
n = 1
while p.next:
n += 1
p = p.next
k = 1
while k < n:
pdummy = dummy
qdummy = dummy.next
while qdummy:
p = qdummy
pt = p
for i in range(k):
qt = pt
pt = pt.next
if pt == None:
break
if not pt:
pdummy.next = qdummy
break
qt.next = None
q = pt
for i in range(k):
qt = pt
pt = pt.next
if not pt:
break
qdummy = pt
qt.next = None

self.myMerge(pdummy, p, q)
if qdummy:
for i in range(2*k):
pdummy = pdummy.next
k <<= 1

return dummy.next``````

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