给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例： 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807

思路

• 将两个链表看成是等长的链表相加，不足位的补0，例如：75+6,看成75+06
• 每一位计算的要考虑上一位的进位问题，并缺当前位计算结束后同样需要更新进位值
• 两个链表各位相加完之后，如果最后的进位值为1，需要在链表上添加一个新的结点（1）

解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution{
public:
    ListNode* addTwoNumbers(ListNode* l1,ListNode* l2){
        ListNode* pre=new ListNode(0);
        ListNode* cur=pre;
        ListNode* p1=l1,*p2=l2;
        int carry=0;                     //进位值
        while(p1!=NULL||p2!=NULL){
            int x=(p1!=NULL)?p1->val:0;  //此位若为空，则补0
            int y=(p2!=NULL)?p2->val:0;  //此位若为空，则补0
            int sum=x+y+carry;
            cur->next=new ListNode(sum%10);
            carry=sum/10;
            cur=cur->next;
            if(p1!=NULL)
                p1=p1->next;
            if(p2!=NULL)
                p2=p2->next;
        }
        if(carry>0)
            cur->next=new ListNode(carry); //添加结点1
        return pre->next;
    }

    void printList(ListNode* l1){
        ListNode* p=l1;
        while(p!=NULL){
            cout<<p->val<<" ";
            p=p->next;
        }
    }

};

int main() {
    std::cout << "Hello, World!" << std::endl;
    ListNode* s1=new ListNode(5);
    s1->next=new ListNode(7);
    ListNode* s2=new ListNode(6);
    Solution s;
    s.printList(s.addTwoNumbers(s1,s2));
    return 0;
}