C++ O(1) extra space except for output. Reverse output instead. Is this cheating?


  • 29
    J

    Idea is to reverse output instead of input. Not sure if this is cheating.

        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            int n1 = 0, n2 = 0, carry = 0;
            ListNode *curr1 = l1, *curr2 = l2, *res = NULL;
            while( curr1 ){ curr1=curr1->next; n1++; }
            while( curr2 ){ curr2=curr2->next; n2++; } 
            curr1 = l1; curr2 = l2;
            while( n1 > 0 && n2 > 0){
                int sum = 0;
                if( n1 >= n2 ){ sum += curr1->val; curr1=curr1->next; n1--;}
                if( n2 > n1 ){ sum += curr2->val; curr2=curr2->next; n2--;}
                res = addToFront( sum, res );
            }
            curr1 = res; res = NULL;
            while( curr1 ){
                curr1->val += carry; carry = curr1->val/10;
                res = addToFront( curr1->val%10, res );
                curr2 = curr1; 
                curr1 = curr1->next;
                delete curr2;
            }
            if( carry ) res = addToFront( 1, res );
            return res;
        }
        ListNode* addToFront( int val, ListNode* head ){
            ListNode* temp = new ListNode(val);
            temp->next = head;
            return temp;
        }
    

  • 0

    much better than those 2 stacks.
    I wrote a recursive version, building from tail to head, but still need to count the length first like you did.


  • 0
    J

    @clydexu Wonder if it is possible to skip the counting part.


  • -1

    @jade86 I only came with an ugly version with one queue.
    x1->x2->x3->x4
    y1->y2
    start with (x1, y1), (x2, y2),
    then we go (x3, y2), (x4, y2), then build the tail and get carry value.

    during return of recursive calls,
    if only one head is changed, we keep push those elements into queue, like
    [x3, x2],
    when we meet (x1, y1), instead of adding those two, we use top element x3 together with y1 and carry value. and push x1 to queue, like [x2, x1],
    finally, deal with extra elements in queue.


  • 0
    J

    @clydexu Interesting solution!


  • 0
    L

    Really nice solution, best of all, why this fucking good solution doesn't vote to highest ?


  • 2
    K

    666666666666


  • 0
    A
    This post is deleted!

  • 5
    V

    @clydexu @loafbit why do you say this is better than 2 stacks? either way we are using O(n) extra space... Storing the reversed intermediate list counts as O(n) space. personally i prefer the stack approach since it's more straightforward and clean. I will say this is an very interesting solution though. Nice idea.


  • -1

    @vikram4 simple because two stacks is trivial, i like special ideas.


  • 0
    V

    @clydexu fair enough, it is an interesting idea. haven't seen one like it before.


  • 0
    D
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // calculate l1 and l2 len.
        int len1 = 0, len2 = 0;
        ListNode *l1_curr = l1, *l2_curr = l2;
        while(l1_curr) {l1_curr = l1_curr->next; len1++;}
        while(l2_curr) {l2_curr = l2_curr->next; len2++;}
        
        // If l1 len larger, swap l1 and l2.
        if(len1 > len2) 
        {
            swap(l1, l2);
            swap(len1, len2);
        }
        
        // add a carry node to l2 and move pointer to allign l1.
        ListNode* carry = new ListNode(0);
        carry->next = l2;        
        l1_curr = l1, l2_curr = carry;
        int i = len2 + 1;
        for(; i > len1; i--)
        {
            l2_curr = l2_curr->next;
        }
        
        // sum up l1 and l2 and count number biggger than 9
        int carry_count = 0;
        for (; i >= 1; i--)
        {
            l2_curr->val += l1_curr->val;
            if (l2_curr->val > 9) carry_count++;
            l2_curr = l2_curr->next;
            l1_curr = l1_curr->next;
        }
        
        // if there is carry, move it to left.
        while(carry_count)
        {
            l2_curr = carry;            
            int count = 0;
            for (i = len2 + 1; i > 1; i--)
            {
                if(l2_curr->next && l2_curr->next->val > 9)
                {
                    l2_curr->val += 1;
                    l2_curr->next->val -= 10;
                }
                if (l2_curr->val > 9) count++;
                l2_curr = l2_curr->next;                
            }
            carry_count = count;
        }
        
        if(carry->val == 1)
            l2 = carry;
        else
            delete carry;
        return l2;
    }

  • 0
    D

    We can save intermediate data by using two digits. The int has TEN digits. Once we detect two digits, we carry it to prev node until no more two digits. If we are forced not to reverse, then we have to iterate. The above code is the implementation.


  • 0
    P

    My super easy to understand recursive version :

    public class Solution {
        int borrow = 0;
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
                int n1 = 0, n2 = 0;
                ListNode ptr = l1;
                while (ptr!= null) {
                    ptr = ptr.next;
                    n1++;
                }
                ptr = l2;
                while(ptr != null) {
                    ptr = ptr.next;
                    n2++;
                }
                ListNode head = null;
                ListNode dummy = null;
                if( n1 > n2)
                    head = addTwoNumbers(l1, l2, n1 - n2);
                else
                    head = addTwoNumbers(l2, l1, n2 - n1);
                if(borrow == 1) {
                    dummy =  new ListNode(borrow);
                    dummy.next = head;
                    return dummy;
                }
                return head;
            }
            
        public ListNode addTwoNumbers(ListNode l1, ListNode l2, int diff) {
            if(l1 == null && l2 == null)
                return null;
            ListNode next = null;
            if(diff > 0)
                next = addTwoNumbers(l1.next, l2, diff - 1);
            else
                next = addTwoNumbers(l1.next, l2.next, diff);
            int sum = 0;
            sum += l1 == null ? 0 : l1.val;
            if(diff == 0)
                sum += l2 == null ? 0 : l2.val;
            sum += borrow;
            borrow = sum / 10;
            sum = sum % 10;
            ListNode curr = new ListNode(sum);
            curr.next = next;
            return curr;
        }
    }
    

  • 0
    Z

    nice solution, while code should explain by itself, maybe this is more readable:

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int len_1 = get_len(l1);
        int len_2 = get_len(l2);
        ListNode *res = NULL;
        
        while(len_1 > 0 && len_2 > 0) {
            int cur_sum = 0;
            if (len_1 >= len_2) {
                cur_sum += l1->val;
                l1 = l1->next;
                len_1--;
            }
            if (len_1 < len_2) {
                cur_sum += l2->val;
                l2 = l2->next;
                len_2--;
            }
            res = add_to_front(cur_sum, res);
        }
        return flatten(res);
    }
    
    ListNode *flatten(ListNode *head) {
        ListNode *res = NULL;
        ListNode *p = head;
        int carry = 0;
        while(p) {
            int cur = carry + p->val;
            res = add_to_front(cur%10, res);
            carry = cur/10;
            p = p->next;
            delete head;
            head = p;
        }
        if (carry) {
            return add_to_front(carry, res);
        }
        return res;
    }
    
    ListNode *add_to_front(int val, ListNode *head) {
        ListNode *h = new ListNode(val);
        h->next = head;
        return h;
    }
    
    int get_len(ListNode *head) {
        if (!head) {
            return 0;
        }
        return 1 + get_len(head->next);
    }

  • 0
    Z

    I think recursion is a more proper answer. You don't have to reverse input or output using recursion. Although recursion call may use O(n) extra space, which is the same as STL container, i.e. stack or vector, it is probably what the question asks for.

    class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            int n1 = length(l1), n2 = length(l2);
            int carry = 0;
            ListNode* h = new ListNode(1);
            h->next = n1 > n2? add_aux(l1, l2, n1-n2, carry):add_aux(l2, l1, n2-n1, carry);
            return carry == 1? h:h->next;
        }
    private:
        int length(ListNode* l) {
            int len = 0;
            while (l != nullptr) {
                len++;
                l = l->next;
            }
            return len;
        }
        ListNode* add_aux(ListNode* l1, ListNode* l2, int k, int& carry) {
            if (l2 == nullptr) return nullptr;
            ListNode* p = new ListNode(l1->val);
            if (k > 0) {
                p->next = add_aux(l1->next, l2, k-1, carry);
            }
            else {
                p->val += l2->val;
                p->next = add_aux(l1->next, l2->next, k, carry);
            }
            p->val += carry;
            carry = p->val/10;
            p->val %= 10;
            return p;
        }
    };
    

  • 0
    B

    @zestypanda hmmm, very impressive recursion. Wondering how long did you take to figure it out


  • 0
    Z

    @banlangen I don't remember. Usually I can write a rather stupid answer in 15-30 minutes, and then I will keep optimizing. I feel it is a good way to improve coding.


  • 0
    N

    This is NOT an O(1) solution, the title is click-baiting.....


  • 0
    A

    I think it is kind of cheating not because you are doing reversing over output, is because you store a number larger than 10 in a node. Ideally we should not do that since one node represents one digit which is 0-9.


Log in to reply
 

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