# How to solve the problem without recursion

• I solved the problem in Java with recursion, merge sort. But I realized that it don't have a constant space complexity.

Every time the function is used, constant space is allocated. The function will be used nearly log(n) times, so the space complexity is log(n).

Maybe it can only be solved without recursion while it has a constant space complexity.

Anyone agrees with me? Who solve it without recursion?

Even though it's not necessary, here is my accepted code: (2 ints and 3 pointers of ListNode are allocated when the funtion is used every time.)

``````public class Solution {
public ListNode sortList(ListNode head) {
int len = 0;
for( ListNode now=head; now!=null; now=now.next )
++len;
if(len<2)
for( int pos=0; pos+1<len/2; ++pos )
tail = tail.next;       //"tail" is the firstHead's tail
tail.next = null;
tail=null;                  //"tail" is the tail of new sorted list now
{
if(tail==null)
{
{
}
else
{
}
}
else
{
{
}
else
{
}
tail = tail.next;
}

}
else if( secondHead==null )
}
}``````

• Here is my solution without recursive calling.

``````
// try to solve it with constant space and O(nlogn) using bottom up merge-sort
class Solution {
public:
ListNode *sortList(ListNode*);
ListNode * mergeList(ListNode *, ListNode*, ListNode*, ListNode*, ListNode * &);
};
ListNode *Solution::sortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
if (head == NULL || head->next == NULL)
int n = 0;
for (ListNode * itr = head; itr != NULL; itr = itr->next)
n++; //caculate the num of nodes
for (int width = 1; width<n; width += width){
ListNode * lhead = head, *rhead = NULL, *ltail = NULL, *rtail = NULL, *last = NULL;
while (true){
if (lhead == NULL)
break;
for (int i = 1; i<width && ltail->next != NULL; i++)
ltail = ltail->next;
if (rhead == NULL)
break;
for (int i = 1; i<width && rtail->next != NULL; i++)
rtail = rtail->next;
ListNode* next = rtail->next;
ListNode * mergetail = rtail;
ListNode * rlt = mergeList(lhead, ltail, rhead, rtail, mergetail);
if (last != NULL)
last->next = rlt;
mergetail->next = next;
last = mergetail;
}
}
}
ListNode * Solution::mergeList(ListNode * lhead, ListNode*ltail, ListNode* rhead, ListNode* rtail, ListNode * & mergeTail){
ListNode * llast = NULL, *rlast = ltail;
ListNode * ritr = rhead, *litr = lhead;
while (ritr != NULL){
ListNode * rnext = ritr == rtail ? NULL : ritr->next;
while (litr != NULL){
ListNode * lnext = litr == ltail ? NULL : litr->next;
if (litr->val <= ritr->val){
llast = litr;
litr = lnext;
}
else break;
}
if (litr == NULL) //indicates all is sorted
break;
rlast->next = ritr->next;
if (llast == NULL){
llast = ritr;
}
else {
llast->next = ritr;
ritr->next = litr;
llast = ritr;
}
ritr = rnext;
}
if (litr != NULL)
mergeTail = ltail;
}
```
```

More on this question (sort in O(nlogn) with constant space):

1. buttom-up merge sort if it is a linked list. (merging can be finished in O(n) time with constant space)
2. heap sort if it is an array.

• Your code has some syntax errors. It can not be compiled! I think you should fix it to pass the LeetCode OJ.
Whatever, thanks for answering and offerring the thoughts.

• The code was copied from my Accepted submission

• for (int i = 1; inext != NULL; i++) what is inext??

• Here is my solution with O(n log n) time and O(n) Space

``````class Solution {
public:
ListNode *sortList(ListNode *head) {
queue<ListNode *> Q;
ListNode *p, *q;
while(p != NULL) {
q = p;
p = p->next;
q->next = NULL;
Q.push(q);
}
ListNode *pa, *pb;
while(Q.size() > 1) {
pa = Q.front();
Q.pop();
pb = Q.front();
Q.pop();
pa = mergeSortedList(pa, pb);
Q.push(pa);
}
return Q.front();
}
private:
ListNode *mergeSortedList(ListNode *la, ListNode *lb) {
ListNode *dummy = new ListNode(-1);
ListNode *pa = la, *pb = lb, *pc = dummy;
while(pa && pb) {
if(pa->val < pb->val) {
pc->next = pa;
pa = pa->next;
} else {
pc->next = pb;
pb = pb->next;
}
pc = pc->next;
}
if(pa) pc->next = pa;
if(pb) pc->next = pb;
pc = dummy->next;
delete dummy;
return pc;
}
};``````

• Recursion adds to the space complexity and this is not acceptable. Leetcode does not catch this.

• Please refer to the below code for constant space complexity bottom up merge sort.

``````/**
* Definition for singly-linked list.
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
class Solution {
ListNode move(ListNode head, int moveBy) {
while(head!=null && moveBy-- > 0)
}
ListNode merge(ListNode loop, int length) {
if (loop==null || loop.next==null)
//this will help break the for loop in the sortList
return null;
ListNode start1 = loop.next;
ListNode end1   = move(start1, length/2-1);
if (end1 == null)
return null;
ListNode start2 = end1.next;
end1.next = null;
ListNode end2 = move(start2, length/2-1);
ListNode end2next = (end2!=null)? end2.next: null;
if (end2next!=null)
end2.next = null;
while (start1!=null || start2!=null) {
if (start2==null || (start1!=null && start1.val < start2.val)) {
loop.next = start1;
start1=start1.next;
loop=loop.next;
} else {
loop.next = start2;
start2=start2.next;
loop=loop.next;
}
}
loop.next=end2next;
return loop;
}
ListNode sortList(ListNode head) {
ListNode dummy = new ListNode(0);
for (int k=2; true; k*=2) {
int nMerges = 0;
ListNode loop = dummy;
while(loop!=null && loop.next!=null) {
loop = merge(loop, k);
nMerges++;
}
//only one sorted run?
if (nMerges<=1)
break;
}
return dummy.next;
}
}``````

• You're using a queue (queue < ListNode * > Q;) to hold all the references, that is linear space, not constant space

• This post is deleted!

• Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example

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