0002. 两数相加

0002. 两数相加 #

  • 标签：链表
  • 难度：容易

一、题目说明 #

描述：给定两个非空的链表 l1 和 l2。分别用来表示两个非负整数，每位数字都是按照逆序的方式存储的，每个节点存储一位数字。

要求：计算两个非负整数的和，并逆序返回表示和的链表。

说明：

  • 每个链表中的节点数在范围 $[1, 100]$ 内。
  • $0 \le Node.val \le 9$。
  • 题目数据保证列表表示的数字不含前导零。

示例：

  • 示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
  • 示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]

二、解题思路 #

1. 数学计算 #

感觉这道题目，考察细心多于算法，因为这个题目的编码逻辑，就是数学加法运算的抽象。

  1. 从个位开始，将两个个位数进行相加，得出结果为个位，如果有进位，则记录进位；
  2. 然后是十位，继续上述逻辑；
  3. 直到两个数字的所有位都计算完毕，得出最终结果。

需要特别注意的是：

  • 两个数字的长度很可能不一致，所以需要用0来补位计算；
  • 计算完毕之后，需要注意是否有进位；
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode result = new ListNode(0);
    ListNode step = result;
    //进位
    int carry = 0;
    while(l1!=null || l2!=null){
        int a = null==l1 ? 0 : l1.val;
        int b = null==l2 ? 0 : l2.val;
        int sum = a + b + carry;
        carry = sum / 10;

        step.next = new ListNode(sum % 10);
        step = step.next;

        l1 = null==l1 ? null : l1.next;
        l2 = null==l2 ? null : l2.next;
    }
    if(carry!=0){
        step.next = new ListNode(carry);
    }
    return result.next;
}