2. 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.

 

思路：

通常想法是用一个int按位相加记录下来总和，再按位放进一个list，但是因为这是道老题，已经超过1500个case了，无论是vector记录还是int记录都会超过内存大小，因此考虑直接在list上进行改变。幸好从左到右是从个位数开始的，否则应该先将list反转过来。思路的话首先判断长度，哪个长哪个就当l1，如果l2更长，swap一下即可，不要忘记同时swap长度。接下来用一个int next记录进位的值，进入while循环，只要l1存在就一直计算，主要内容是如果有进位，就l1的值加next，如果有l2，就l1的值加l2的值。此时l1的值，假设为temp，temp%10就是这一位的值，temp/10就是下一位的进位，即新的next。出了循环以后，如果还有新的next，那就是新的位了，考虑到l1的旧的最后一位可能是9，还有进位，因此出了while循环后，如果next大于0，则l1下新建一个node用来储存新的位。

 

代码：

/**
 * 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) {
        if(!l1)
            return l2;
        if(!l2)
            return l1;
        int len1 = getlen(l1);
        int len2 = getlen(l2);  
        if(len1<len2)
        {
            swap(l1,l2);
            swap(len1,len2);
        }
        ListNode* root=l1;
        int next=0;
        while(l1)
        {
            if(l2)
            {
                l1->val=l1->val+l2->val;
                l2=l2->next;
            }
            l1->val+=next;
            next=l1->val/10;
            l1->val=l1->val%10;
            if(!l1->next)
                break;
            l1=l1->next;
        }       
        if(next>0)
            l1->next=new ListNode(next);
        return root;
    }
private:
    int getlen(ListNode* root)
    {
        int count =0;
        while(root)
        {
            count++;
            root=root->next;
        }
        return count;
    }
};