2. Add Two Numbers

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(0);
        ListNode* res = head;
        int carry = 0;
        
         while (l1 != nullptr || l2 != nullptr) {
            int fir = 0;
            int sec = 0;
            if (l1 != nullptr) { fir = l1->val; }
            if (l2 != nullptr) { sec = l2->val; }
            
            int sum = fir + sec + carry;
            carry = sum / 10;
            int lastDigit = sum % 10;
            
            res->next = new ListNode(lastDigit);

            l1 = l1 != nullptr ? l1->next : nullptr;
            l2 = l2 != nullptr ? l2->next : nullptr;
            res = res->next;
        }

        if (carry > 0) {
            res->next = new ListNode(carry);
            res = res->next;
        }
        
        return head->next;
    }
};

Complexity

  • Time Complexity: O(N+M), where N and M are the number of nodes of l1 and l2 respectively.
  • Space Complexity: O(N), where N is the number of nodes of res.

All Solutions