- 题目：2. 两数相加
- 难度：中等
- 分类：链表
- 解决方案：链表的遍历
题目描述
给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
注意：您可以假设除了数字0之外，这两个数都不会以0开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
分析
这个题理解起来难度不大，就是将数字从个位数开始将数字放到链表的各个结点上，如下所示：
链表表示数字.png
然后两个链表的对应位置上的数字相加，将相加的值保存到结果链表中。这里需要注意两个关键点：一是如果两个值相加大于9该怎么办？二是两个链表长度不一致该怎么办？
对于关键点一：我们需要借助一个进位标识carry，当两数之和大于9时将carry标识为1，否则标识为0。
对于关键点二：我们以最长链表作为终点，对于较短链表对应位置的数值，我们用0来补齐。
下面分析一个具体实例，该实例包含上述两个关键点，如下图所示：
两数相加.png
如上图所示，数字342的链表较短，数字7465的链表较长。当两个数字的第二个结点相加时，它们的和为10，这时就需要进位，即carry=1，且将个位数保留作为结果链表的值。当较短的链表指向为null结点时，较长的链表指向的值为7，这需要将较短链表的值设置为0，即结果为0+7。
通过上面分析后，再看看如下java便一目了然。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 创建结果链表的头节点，默认该节点中的value为-1
ListNode dummy = new ListNode(-1);
ListNode pre = dummy;
// 进位标识carry，默认为0
int carry = 0;
// 遍历链表，当两个链表都为空时，退出
while(l1 != null || l2 != null){
// 判断该节点是否为空，当结点为空时，用0补齐；不为空时，加数即为节点的值
int d1 = (l1 == null) ? 0 : l1.val;
int d2 = (l2 == null) ? 0 : l2.val;
// 对结点求和，注意：求和是需要考虑到进位
int sum = d1 + d2 + carry;
// 更新进位标识
carry = (sum >= 10) ? 1 : 0;
// sum%10标识求和的个位数，将其保存到结果链表中
pre.next = new ListNode(sum % 10);
pre = pre.next;
if(l1 != null) l1 = l1.next;
if(l2 != null) l2 = l2.next;
}
// 重点，这是一个特殊情况，当两个链表计算完后，
// 还需要判断进位标识是否为1，如果为1，如23+81=104，需要创建一个结点保存最高位
if(carry == 1)
pre.next = new ListNode(1);
return dummy.next;
}
}
两数相加计算结果.png
对于时间复杂度和空间复杂度，该题都为O(n)。
Github地址
参考链接
更多文章，请扫描二维码关注『算法半岛』
