LeetCode-2 两数相加

Leefs 2020-02-16 PM 1799℃ 0条

# LeetCode-2 两数相加

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

### 题目描述

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

**示例：**

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

### 分析

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

![33.LeetCode-2 两数相加01.png][1]

然后两个链表的对应位置上的数字相加，将相加的值保存到结果链表中。这里需要注意两个关键点：**一是如果两个值相加大于9该怎么办？二是两个链表长度不一致该怎么办？**

对于关键点一：我们需要借助一个进位标识carry,当两位数之和大于9时将carry标识为1，否则标识为0.

对于关键点二：我们以最长链表作为终点，对于较短链表对应位置的数值，我们用0来补齐。
下面分析一个具体实例，该实例包含上述两个关键点，如下图所示：

![33.LeetCode-2 两数相加02.png][2]

如上图所示，数字342的链表较短，数字7465的链表较长。当两个数字的第二个结点相加时，它们的和为10，这时就需要进位，即`carry=1`，且将个位数保留作为结果链表的值。当较短的链表指向为`null`结点时，较长的链表指向的值为7，这需要将较短链表的值设置为0，即结果为0+7。

通过上面分析后，再看看如下`java`便一目了然。

```java
public class Solution02 {

public ListNode addTwoNumbers2(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);
            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;
    }
}
class ListNode{
    int val;
    ListNode next;
    public ListNode(int val){
        this.val = val;
    }

}
```

*附：[原文链接](https://www.jianshu.com/p/a86b8c8dcfa5)*

[1]: https://lilinchao.com/usr/uploads/2020/02/4044063671.png
  [2]: https://lilinchao.com/usr/uploads/2020/02/1467780105.png

标签: none

非特殊说明，本博所有文章均为博主原创。

如若转载，请注明出处：https://lilinchao.com/archives/614.html

上一篇 LeetCode-1.两数之和

下一篇数据结构和算法学习--二叉排序树

LeetCode-2 两数相加

评论已关闭

栏目分类

标签云

友情链接申请

LeetCode-2 两数相加

评论已关闭

 栏目分类

标签云

友情链接申请

栏目分类

标签云

友情链接申请