Title Source: LeetCode

https://leetcode-cn.com/problems/add-two-numbers

Give you two non empty linked lists to represent two non negative integers. Each number is stored in reverse order, and each node can only store one digit.

Please add the two numbers and return a linked list representing sum in the same form.

You can assume that neither number starts with 0 except the number 0.

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], L2 = [9,9,9]
Output: [8,9,9,9,0,0,1]
 

Tips:

The number of nodes in each linked list is within the range [1, 100]
0 <= Node.val <= 9
The number represented in the title data guarantee list does not contain leading zeros

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(-1);//Linked list for storing results
        ListNode* h=head;//Move pointer
        int sum=0;//Sum result of each bit
        bool carry=false;//Carry flag
        while(l1!=NULL||l2!=NULL)
        {
            sum=0;
            if(l1!=NULL)
            {
                sum+=l1->val;
                l1=l1->next;
            }
            if(l2!=NULL)
            {
                sum+=l2->val;
                l2=l2->next;
            }
            if(carry)//Carry sum++
                sum++;
            h->next=new ListNode(sum%10);//Insert results
            h=h->next;
            carry=sum>=10?true:false;//Judge whether there is carry
        }
        if(carry)//Judge whether the highest bit has carry
        {
            h->next=new ListNode(1);
        }
        return head->next;
    }

};

This solution uses an addition template, which is as follows:

< formula >

Current bit = (A Current bit of + B Current bit of + carry carry) % 10
 be careful, AB After adding both numbers, finally judge the carry carry, If the carry is not 0, it is added in front.

< addition template >

while ( A have not finished || B have not finished)
    A Current bit of
    B Current bit of

    and = A Current bit of + B Current bit of + carry carry

    Current bit = and % 10;
    carry = and / 10;

Is there any carry

Addition template Author: lilyunoke
Original article link: https://leetcode-cn.com/problems/add-to-array-form-of-integer/solution/989-ji-zhu-zhe-ge-jia-fa-mo-ban-miao-sha-8y9r/

The idea of this addition template is very clear. In this question, carry represents carry, which is a bool variable. Because the two numbers are added, the maximum carry is 9 + 9, so carry is 0 or 1, which can be represented by Boolean variables. If you add more numbers or multiply two numbers, you can't use Boolean variables. You need to use int.

When judging the carry, the lowest bit (bit) has no carry, and the carry of the highest bit should be judged outside the while loop.

There is another non recursive solution:

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode(0);
        ListNode cursor = root;
        int carry = 0;
        while(l1 != null || l2 != null || carry != 0) {
            int l1Val = l1 != null ? l1.val : 0;
            int l2Val = l2 != null ? l2.val : 0;
            int sumVal = l1Val + l2Val + carry;
            carry = sumVal / 10;
            
            ListNode sumNode = new ListNode(sumVal % 10);
            cursor.next = sumNode;
            cursor = sumNode;
            
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        
        return root.next;
    }
}

The difference between the two solutions is that the second solution puts the judgment of carry in the while loop and replaces the if judgment with conditional judgment. This makes the code simpler and faster to execute.

Another point is that this problem is in reverse order, but the input and output forms are the same. They are in reverse order, so you can insert it directly from the back of the linked list. There is no place that needs special attention.