leetcode *2. 两数相加（模拟十进制加法，模板）（2020.10.4）

【题目】*2. 两数相加

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

示例：

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

【解题思路1】模拟十进制加法

不管是几进制，加法都可以在此基础上改写，无论给的是链表、数组、字符串，其实乘法也可以但是乘完了还要移位相加改动比较大比较麻烦所以下面仅是加法的模板。

两个数同步从低位往高位遍历，while循环结束条件是两个数都遍历结束while (l1 != null || l2 != null)设置进位 carry，初始值为 0每次遍历的时候都使用三元表达式提取出两个数当前要相加的位 int n1 = l1 != null ? l1.val : 0;这样写的优势是可以不管两个数的长度是否一致，其实就是再比较短的数前面补0的效果取出当前要相加的位的数字 n1 和 n2，计算 sum = n1 + n2 + carry更新 carry = sum / 10， 而这一轮相加的结果个位就是 sum % 10，从低位往高位填入这个结果当 while循环 结束的时候说明两个数都遍历完了，但是还要考虑一下最后还有进位的情况，比如 1 + 99 = 100，即最后的和的位数比原来两个数最大位数还多一位的情况，所以最后要做一个 if (carry > 0)判断 // 这段代码是模板重点的地方，取数字存结果根据题目给的形式而定 int n1 = l1 != null ? l1.val : 0; int n2 = l2 != null ? l2.val : 0; int sum = n1 + n2 + carry; carry = sum / 10;

将while循环结束条件改为while (l1 != null || l2 != null || carry > 0)，这样的话循环结束后就不需要判断if (carry > 0)了。相当于先将位数较少的数前面补0保持两数位数一致，再在两数前面再补一个0，如果最一轮循环 carry > 0 就是 0 + 0 + carry，效果一样的

1. 官方给的是没有头结点的链表，判断稍微繁琐了一点

class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode head = null, tail = null; int carry = 0; while (l1 != null || l2 != null) { int n1 = l1 != null ? l1.val : 0; int n2 = l2 != null ? l2.val : 0; int sum = n1 + n2 + carry; carry = sum / 10; if (head == null) { head = tail = new ListNode(sum % 10); } else { tail.next = new ListNode(sum % 10); tail = tail.next; } if (l1 != null) l1 = l1.next; if (l2 != null) l2 = l2.next; } if (carry > 0) { tail.next = new ListNode(carry); } return head; } }

2. 改进写法，创造一个头节点，最后返回头结点的next

class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode head = new ListNode(0), cur = head; int carry = 0; while (l1 != null || l2 != null) { int n1 = l1 != null ? l1.val : 0; int n2 = l2 != null ? l2.val : 0; int sum = n1 + n2 + carry; carry = sum / 10; cur.next = new ListNode(sum % 10); cur = cur.next; if (l1 != null) l1 = l1.next; if (l2 != null) l2 = l2.next; } if (carry > 0) cur.next = new ListNode(carry); return head.next; } } class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* dummpy = new ListNode(0); ListNode* cur = dummpy; int carry = 0; while(l1 != nullptr || l2 != nullptr) { int num1 = l1 == nullptr ? 0 : l1 -> val; int num2 = l2 == nullptr ? 0 : l2 -> val; int sum = num1 + num2 + carry; carry = sum / 10; cur -> next = new ListNode(sum % 10); cur = cur -> next; if(l1 != nullptr) l1 = l1 -> next; if(l2 != nullptr) l2 = l2 -> next; } if(carry > 0) cur -> next = new ListNode(carry); return dummpy -> next; } };