2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807
写法一：创建新节点
/*** 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, int carry = 0) {//l1 l2 为当前遍历的节点 carry 为进位if(l1 == nullptr && l2 == nullptr && carry == 0){//递归边界return nullptr;}int s = carry;if(l1){s += l1-> val;//累加进位与节点值l1 = l1->next;}if(l2){s += l2->val;l2 = l2->next;}//s 除以 10 的余数为当前节点值，商为进位return new ListNode(s % 10,addTwoNumbers(l1,l2,s/10));}
};
写法二：原地修改
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry = 0) {if(l1 == nullptr && l2 == nullptr){//递归边界return carry ? new ListNode(carry) : nullptr;}if(l1 == nullptr){//如果l1是空的，那么此时l2一定是不是空节点swap(l1,l2);//交换 l1 与 l2 保证l1非空从而简化代码}int sum = carry + l1->val + (l2 ? l2->val : 0);//节点值和进位加在一起l1->val = sum % 10;//每个节点保存一个数为（直接修改原链表）l1->next = addTwoNumbers(l1->next,(l2 ? l2->next : nullptr), sum / 10);return l1;}
};