[leetcode] 2. Add two numbers (user-defined listnode), medium

1、 subject

Here are two for you Non empty The linked list of , Represents two nonnegative integers . Each of them is based on The reverse Stored in , And each node can only store a Numbers .

Please add up the two numbers , And returns a linked list representing sum in the same form .

You can assume that in addition to the numbers 0 outside , Neither of these numbers 0 start .

【 Example 1 】

Input ：l1 = [2,4,3], l2 = [5,6,4]
Output ：[7,0,8]
explain ：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]

2、 answer

2.1 Official website answer

/** * 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 = nullptr, *tail = nullptr;
        int tab = 0;   // carry 
        while (l1 || l2) 
        {
    
            int n1 = l1 ? l1->val: 0;
            int n2 = l2 ? l2->val: 0;
            int sum = n1 + n2 + tab;
            tab = sum / 10;
            if (!head)    // Empty list , Only when the single digit addition is performed for the first time head It's empty .
                head = tail = new ListNode(sum % 10);
                // Special attention should be paid to the fact that empty linked lists cannot be directly linked to val assignment , Only use new assignment .
            else 
            {
    
                tail->next = new ListNode(sum % 10);
                tail = tail->next;
            }           
            if (l1) 
                l1 = l1->next;            
            if (l2) 
                l2 = l2->next;            
        }
        if (tab > 0)   // Last carry  
            tail->next = new ListNode(tab);        
        return head;                     
    }
};

Although the official answer runs for a long time , Only defeated the whole country 5% Users of . But its algorithm idea is still commendable , The most important idea is to introduce head pointers head And tail pointer tail, In the process of processing, only tail To iterate , Finally back to head, This is much more convenient .

I used only one pointer to do it , When you want to add elements at the end of the linked list, you need to use the pointer from the beginning while Iterate to tail pointer , It will be very troublesome , It's also time-consuming . Or both head and tail It will be much easier to use .

2.2 Simplify the answer

class Solution {
    
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            
        ListNode* head = new ListNode(0), *cur = head;     
        int tab = 0; 
        while (l1 || l2)
        {
    
            if (l1) 
            {
    
                tab += l1->val;
                l1 = l1->next;
            }
            if (l2) 
            {
    
                tab += l2->val;
                l2 = l2->next;
            }               
            cur->next = new ListNode(tab % 10);
            cur = cur->next;
            tab /= 10;
        }
        if (tab>0) 
            cur->next = new ListNode(tab);
        return head->next;                   
    }
};

Its basic idea is no different from the official answer , Just some simplification , The implementation time has exceeded that of the whole country 60.24% Users of .

3、 Knowledge point

（1） Be familiar with the question mark operator .

（2） Remainder （%） Use ：3%10=3,20%10=0,18%10=8
The remainder operation can avoid judgment sum And 10 The size of the relationship .

（3） Custom list LIstNode See my other blog for the operation of C++ Custom one-way linked list ListNode, Use at the same time head and tail Your ideas are well worth learning .