• 题目：2. 两数相加
• 难度：中等
• 分类：链表
• 解决方案：链表的遍历

<!-- more -->

题目描述

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

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

分析

这个题理解起来难度不大，就是将数字从个位数开始将数字放到链表的各个结点上，如下所示：

然后两个链表的对应位置上的数字相加，将相加的值保存到结果链表中。这里需要注意两个关键点：一是如果两个值相加大于9该怎么办？二是两个链表长度不一致该怎么办？
对于关键点一：我们需要借助一个进位标识carry，当两数之和大于9时将carry标识为1，否则标识为0。
对于关键点二：我们以最长链表作为终点，对于较短链表对应位置的数值，我们用0来补齐。
下面分析一个具体实例，该实例包含上述两个关键点，如下图所示：

如上图所示，数字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;  
    }
}

对于时间复杂度和空间复杂度，该题都为O(n)。

Github地址

LeetCode-2 两数相加

参考链接

2. 两数之和

更多文章请添加公众号：算法半岛（扫描上图二维码即可关注）