Short 32ms C++ solution with explanation


  • 1
    D

    We iterate through both lists adding the digits and maintaining a carry. If one list is exhausted first, we have to continue adding the digits from the other number. At the end we may need to add an extra digit if carry is nonzero.

    Here I'm using comparisons to compute the next digit and the carry which should be faster than using mod but I haven't tested that.

    class Solution {
    public:
        pair<int, int> addTwoDigits(int d1, int d2, int carry_in) {
            int sum = d1 + d2 + carry_in;
            int digit = sum > 9 ? sum - 10 : sum, carry = sum > 9 ? 1 : 0;
            return {digit, carry};
        }
    
        ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
            
            ListNode h(0);
            auto head = &h, curr = head;
            pair<int, int> digit_carry {0, 0};
            while (l1 && l2) {
                digit_carry = addTwoDigits(l1->val, l2->val, digit_carry.second);
                curr->next = new ListNode(digit_carry.first);
                curr = curr->next, l1 = l1->next, l2 = l2->next;
            }
            auto l = l1 ? l1 : l2;
            while (l) {
                digit_carry = addTwoDigits(l->val, 0, digit_carry.second);
                curr->next = new ListNode(digit_carry.first);
                curr = curr->next, l = l->next;
            }
            if (digit_carry.second != 0) {
                curr->next = new ListNode(digit_carry.second);
            }
            return head->next;    
        }
    };

Log in to reply
 

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