题目：
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字0之外，这两个数都不会以0开头。
示例：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807
输入：l1 = [0], l2 = [0]
输出：[0]
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
提示：
[1, 100] 内0 <= Node.val <= 9思路：模拟
由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。我们可以同时遍历两个链表，计算他们的和。本题没有太大的难度，但是有几种不同的操作顺序，选择不同的顺序，代码编写难度会不同，效率也会有细微差别。
新建链表结点or利用已有结点，显然利用已有结点构造链表在时间上快于新建结点，但编写难度比新建结点复杂。一边遍历一边处理数据or构造完链表再处理数据，显然第一种时间更快（只需一次遍历），同样编写代码稍复杂。
我更偏向于运行效率，所以我利用l1结点建立链表newl，将计算结果记录在l1.val中，将进位值加到下一结点，处理直到某一链表遍历完成，此时会出现三种情况。（1）l1.next == null && l2.next != null（2）l1.next != null && l2.next == null（3）l1.next == null && l2.next == null。只有第一种情况会导致无法利用l1结点构造链表，需要特殊处理，也很容易实现，将l1.next = l2.next，就将剩余全部结点链接到newl中，接着遍历进行处理，最后一个结点需单独处理，因为如果最后一结点值大于10，则需要进位，就需要新建一结点保存进位值，最后将新建结点加入newl即完成。
// Java代码 class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode newl = l1;// 利用l1构造和链表 while (l1.next != null && l2.next != null) {// 处理都不为空的正常情况 l1.val += l2.val;// 将l1和l2的值的和保存在l1 if (l1.val >= 10) {// 进行/和%操作处理 l1.next.val += l1.val / 10;// 将进位加到l1.next l1.val %= 10;// 更新当前结点值 } l1 = l1.next;// 指针后移 l2 = l2.next;// 指针后移 } if (l2.next != null) { // 处理l2.next == null的特殊情况，另外两种情况不需要处理 // 即l1.next和l2.next都为空;以及l1.next == null l1.next = l2.next; } l1.val += l2.val;// 将l1和l2的值的和保存在l1 while (l1.next != null) {// 遍历剩下的结点 if (l1.val >= 10) {// 进行/和%操作处理 l1.next.val += l1.val / 10;// 将进位加到l1.next l1.val %= 10;// 更新当前结点值 } l1 = l1.next;// 指针后移 } if (l1.val >= 10) {// 处理最后一个结点的特殊情况 // 后边已无结点，需新建 ListNode newnode = new ListNode(l1.val / 10, null); l1.next = newnode;// 将新结点加入链表 l1.val %= 10;// 更新当前结点值 } return newl;// 返回最终的和链表 } }
// C++代码 class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* newl = l1;// 利用l1构造和链表 while (l1->next != nullptr && l2->next != nullptr) {// 处理都不为空的正常情况 l1->val += l2->val;// 将l1和l2的值的和保存在l1 if (l1->val >= 10) {// 进行/和%操作进行处理 l1->next->val += l1->val / 10;// 将进位加到l1.next l1->val %= 10;// 更新当前结点值 } l1 = l1->next;// 指针后移 l2 = l2->next;// 指针后移 } if (l2->next != nullptr) { // 处理l2.next == null的特殊情况，另外两种情况不需要处理 // 即l1.next和l2.next都为空;以及l1.next == null l1->next = l2->next; } l1->val += l2->val;// 将l1和l2的值的和保存在l1 while (l1->next != nullptr) {// 遍历剩下的结点 if (l1->val >= 10) {// 进行/和%操作进行处理 l1->next->val += l1->val / 10;// 将进位加到l1.next l1->val %= 10;// 更新当前结点值 } l1 = l1->next;// 指针后移 } if (l1->val >= 10) {// 处理最后一个结点的特殊情况 // 后边已无结点，需新建 ListNode* newnode = new ListNode(l1->val / 10, nullptr); l1->next = newnode;// 将新结点加入链表 l1->val %= 10;// 更新当前结点值 } return newl;// 返回最终的和链表 } };
原文：https://www.cnblogs.com/Acx7/p/14612944.html