How to solve the problem without recursion


  • 10
    Y

    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)
            	return head;
            ListNode firstHead, secondHead, tail;
            firstHead = tail = secondHead = head;
            for( int pos=0; pos+1<len/2; ++pos )
            	tail = tail.next;       //"tail" is the firstHead's tail
            secondHead = tail.next;
            tail.next = null;
            firstHead = sortList(firstHead);
            secondHead = sortList(secondHead);
            tail=null;                  //"tail" is the tail of new sorted list now
            while( firstHead!=null&&secondHead!=null )
            {
            	if(tail==null)
            	{
            		if(firstHead.val<=secondHead.val)
            		{
            			tail = head = firstHead;    //"head" becomes the head of new sorted list
            			firstHead = firstHead.next;
            		}
            		else
            		{
            			tail = head = secondHead;
            			secondHead = secondHead.next;
            		}
            	}
            	else
            	{
            		if(firstHead.val<=secondHead.val)
            		{
            			tail.next = firstHead;
            			firstHead = firstHead.next;
            		}
            		else
            		{
            			tail.next = secondHead;
            			secondHead = secondHead.next;
            		}
            		tail = tail.next;
            	}
            	
            }
            if( firstHead==null )
            	tail.next = secondHead;
            else if( secondHead==null )
            	tail.next = firstHead;
            return head;
        }
    }

  • 1

  • 0
    L

    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)
    		return head;
    	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;
    			ltail = lhead;
    			for (int i = 1; i<width && ltail->next != NULL; i++)
    				ltail = ltail->next;
    			rhead = ltail->next;
    			if (rhead == NULL)
    				break;
    			rtail = rhead;
    			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;
    			if (lhead == head)
    				head = rlt;
    			lhead = next;
    		}
    	}
    	return head;
    }
    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){
    			ritr->next = lhead;
    			lhead = ritr;
    			llast = ritr;
    		}
    		else {
    			llast->next = ritr;
    			ritr->next = litr;
    			llast = ritr;
    		}
    		ritr = rnext;
    	}
    	if (litr != NULL)
    		mergeTail = ltail;
    	return lhead;
    }
    
    

    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.

  • 0
    Y

    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.


  • 0
    L

    The code was copied from my Accepted submission


  • 0
    G

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


  • -1
    I

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

    class Solution {
    public:
        ListNode *sortList(ListNode *head) {
            if(head == NULL || head->next == NULL) return head;
            queue<ListNode *> Q;
            ListNode *p, *q;
            p = head;
            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;
        }
    };

  • 0
    U

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


  • 8
    U

    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)
                    head=head.next;
                return head;
            }
            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);
                dummy.next = head;
                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;
            }
        }

  • 0
    P

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


  • 0
    L
    This post is deleted!

  • 0
    S

    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


Log in to reply
 

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