两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。每个链表中的节点数在范围 [1, 100] 内，0 <= Node.val <= 9，题目数据保证列表表示的数字不含前导零。相关标签：递归, 链表, 数学。

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. 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. Related Topics: Recursion, Linked List, Math.

  1. Input: l1 = [2,4,3], l2 = [5,6,4]
  2. Output: [7,0,8]
  3. Explanation: 342 + 465 = 807.
  1. Input: l1 = [0], l2 = [0]
  2. Output: [0]
  1. Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
  2. Output: [8,9,9,9,0,0,0,1]

这题其实是一个模拟题，让我们去模拟一下我们小学学过的列竖式的加法。题意说用链表来表示一个数，注意链表在表示的时候是反着来表示的。然后给我们两个用链表表示的数然后让我们去算一下它们的和并且这个和也要用链表表示。

这题的话其实就是让我们回忆一下我们小学的数学是这么学的那么这里就这么做。小学数学里面这么列竖式我们这里就这么做就可以了。举个例子，小学数学两个数相加的时候先算个位，由于链表是从右往左看的，所以个位先看两个链表的第一个数，第一个数相加模上十的余数(因为我们只保留个位)它就是我们和的第一位数。这里可能会有进位，进位有可能是0有可能是1，这两个数如果相加大于等于十的话进位就是1，如果小于十进位就是0。然后下一个数应该就是两个链表相对应位置的两个数相加之后再加上进位，然后对十取模的结果的余数就是我们和的十位数数字，以此类推…

所以这里面其实是有规律的，我们从个位开始算，每一位的在计算的时候要算三个数字：第一个链表的这一位的数值加上第二个链表这一位的数值加上进位，然后我们和的这位数字应该是我们三位数字之和的个位。然后如果和大于十的时候要往前进一位，否则不往前进一位。

我们在用代码实现的时候其实就是从个位开始循环就可以了，循环的时候看一下如果说某一个链表如果没有循环完那么就要一直做，如果我们有进位的话如果进位不是零的话那么也要一直做，直到做到每个链表循环完了并且进位也为零为止。思路就是小学的列竖式，

为了方便我们一般会定义一个虚拟头节点，因为我们要插入的时候这个定义了一个虚拟头节点的话就不用判断当前节点是不是第一个节点了，就方便很多。凡事需要特判第一个点的时候我们都可以加一个虚拟头节点，这是一个小技巧。然后我们来看一下代码怎么写：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  14.         // 答案链表的虚拟头节点dummy，cur表示我们当前和的尾节点
  15.         auto dummy=new ListNode(-1),cur=dummy;
  16.         int t=0;
  17.         while(l1 || l2 || t) {
  18.             if(l1) t+=l1->val,l1=l1->next;
  19.             if(l2) t+=l2->val,l2=l2->next;
  20.             cur=cur->next=new ListNode(t%10);
  21.             t/=10;
  22.         }
  23.         return dummy->next;
  24.     }
  25. };
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dum := new(ListNode)
    cur := dum
    carry := 0

    for(l1 != nil || l2 != nil || carry > 0){
        cur.Next = new(ListNode)
        cur = cur.Next
        if l1 != nil{
            carry += l1.Val
            l1 = l1.Next
        }
        if l2 != nil{
            carry += l2.Val
            l2 = l2.Next
        }
        cur.Val = carry % 10
        carry /= 10
    }
    return dum.Next
}