Add two numbers inplace without using additional dummy nodes


  • 0
    W

    Just saw an interview question which is to add two numbers without using additional variables. The approach is straight forward, I did it by enumerating the three possiblities (i.e. l1 is longer than l2, l1 has the same size as l2, l1 is shorter than l2). The result is stored in l1. I know that this ruins the original lists, but it does give the correct result and does not require any unnecessary additional new nodes to be added when the two lists have different lengths.

        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            ListNode *head = l1;
            int carry = 0;
            while(l1->next && l2->next){
                l1->val += l2->val + carry;
                carry = l1->val / 10;
                l1->val %= 10;
                
                l1 = l1->next;
                l2 = l2->next;
            }
            
            l1->val += l2->val + carry;
            carry = l1->val / 10;
            l1->val %= 10;
            
            if(!l1->next && !l2->next){
                if(carry) l1->next = new ListNode(1);
                return head;
            }
            if(!l1->next && l2->next) { l1->next = l2->next; }
            l1 = l1->next;
            
            while(l1){
                l1->val += carry;
                carry = l1->val / 10;
                l1->val %= 10;
                if(l1->next) { l1 = l1->next; }
                else { break; }
            }
            if(carry){
                l1->next = new ListNode(1);
            }
            
            return head;
        }
    

Log in to reply
 

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