36ms solution with comments


  • 0
    P
        class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            if(l1 == NULL || l2 == NULL) return l1;
            ListNode* pl1 = l1;
            ListNode* pl2 = l2;
            ListNode* ret = pl1;
            ListNode* tail = NULL;
            
            int carry = 0;
            // handle the common part
            while(pl1 && pl2) {
                pl1->val += pl2->val + carry;
                if(pl1->val >= 10) {
                    pl1->val %= 10;
                    carry = 1;
                } else {
                    carry = 0;
                }
                pl2->val = pl1->val;
                // if they have same len and remaining carry, save the last node before carry on
                if(!pl1->next && !pl2->next && carry) {
                    tail = pl1;
                }
                pl1 = pl1->next;
                pl2 = pl2->next;
            }
            
            // handle the remaining carry and sublist
            ListNode *pCarry = NULL;
            if (tail) {
                // have the same len and there was carry left
                if(carry) {
                    pCarry = new ListNode(1);
                    tail->next = pCarry;
                }
            } else {
                // handle the sublist
                ListNode* tmp = NULL;
    
                if(pl1) {
                    ret = l1;
                    tmp = pl1;
                } else {
                    ret = l2;
                    tmp = pl2;
                }
                // only if there is remaining carry, should we continue the calculation
                while(tmp && carry) {
                    tmp->val += carry;
                    if(tmp->val >= 10) {
                        tmp->val %= 10;
                        carry = 1;
                    } else {
                        carry = 0;
                    }
                    if(!tmp->next && carry) {
                        pCarry = new ListNode(1);
                        tmp->next = pCarry;
                        break;
                    } else {
                        tmp = tmp->next;
                    }
                }
            }
            return ret;
        }
    };

Log in to reply
 

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