Add Two Numbers medium

Problem Statement

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1

Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.

Example 2

Input: l1 = [0], l2 = [0] Output: [0]

Example 3

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]

Steps

1. Initialization: Create a dummy node head to simplify the result list handling. Initialize a carry variable to 0. Set a current pointer to the head.

2. Iteration: While either l1 or l2 is not null, or carry is not 0:

   • Get the values of the current nodes in l1 and l2. If a list is finished, use 0 as the value.
   • Calculate the sum: sum = val1 + val2 + carry.
   • Update carry: carry = sum / 10.
   • Create a new node with the value sum % 10 and append it to the current node.
   • Move current to the newly created node.
   • Move l1 and l2 to their next nodes.

3. Return: Return the next node after the dummy head (head->next).

Explanation

The algorithm simulates addition as we would do it manually. We iterate through the linked lists, adding digits from both lists along with the carry from the previous addition. The modulo operator (%) gives us the last digit of the sum, and integer division (/) gives us the carry to be added to the next digit's sum. The dummy head simplifies the code by providing a starting point for the result list, avoiding special handling for the first node.

Code

/**
 * 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); // Dummy node
        ListNode* current = head;
        int carry = 0;

        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int val1 = (l1 != nullptr) ? l1->val : 0;
            int val2 = (l2 != nullptr) ? l2->val : 0;
            int sum = val1 + val2 + carry;
            carry = sum / 10;

            current->next = new ListNode(sum % 10);
            current = current->next;

            if (l1 != nullptr) l1 = l1->next;
            if (l2 != nullptr) l2 = l2->next;
        }

        return head->next;
    }
};

Complexity

• Time Complexity: O(max(m, n)), where m and n are the lengths of the two linked lists. We iterate through the lists once.
• Space Complexity: O(max(m, n)) in the worst case, as the resulting linked list can have a length equal to the maximum length of the input lists plus one (for a potential extra carry). The space used by the variables is constant.