Leetcode Study Day 28

Add Two Numbers

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]
 

Constraints:

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

Solution

The solution is to use a linked list to store the sum of two digits. The carry is stored in a variable. The sum of two digits is the sum of the two digits plus the carry. The carry is the sum divided by 10. The sum is the sum mod 10. The sum is the new node of the linked list. The carry is the carry of the next iteration. Once we compute the carry and the sum value, we create a new ListNode with the sum value, and then linked the current Node to this new ListNode, and then set the temp, which is the current node to the next one. The iteration stops when both linked lists are empty and the carry is 0.

/**
 * 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();
        ListNode* temp = head;
        int carry = 0;
        while (l1 || l2|| carry ){
            int sum = 0;
            if (l1){
                sum += l1->val;
                l1 = l1->next;
            }
            if(l2){
                sum += l2->val;
                l2 = l2->next;
            }
            sum += carry;
            carry = sum/10;
            ListNode *head =  new ListNode(sum%10);
            temp -> next =head;
            temp = temp->next;
        }
        return head -> next;
    }
};