LeetCode--2.两数相加

1 题目描述

给你两个 非空 的链表, 表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的, 并且每个节点只能存储 一位 数字

请你将两个数相加, 并以相同形式返回一个表示和的链表
你可以假设除了数字 0 之外, 这两个数都不会以 0 开头
示例 1:

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

示例 2:

输入: l1 = [0],  l2 = [0]
输出: [0]
1
2

示例 3:

输入: l1 = [9, 9, 9, 9, 9, 9, 9],  l2 = [9, 9, 9, 9]
输出: [8, 9, 9, 9, 0, 0, 0, 1]
1
2

提示:

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

2 解题思路

从题目描述看, 是从0 ~ n 结点遍历 ListNode l1, l2, 计算相同位置节点的和, 需要注意进位

1. 计算相同位置节点的和: int sum = l1.val + l2.val + increase, 其中 increase 是进位
2. 当前节点需要保存的数据 sum % 10, 计算进位 increase = sum / 10
3. 需要考虑 l1 和 l2 遍历时, 可能会存在遍历完成时, 获取当前节点 val 时, 需要补充为 0
4. 将 l1 和 l2 指向 next 节点

2.1 代码实现

/**  
 * 1. 需要考虑两个链表为空的情况  
 * 2. 需要考虑计算进位问题  
 * 3. 需要考虑两个链表长度不一致, 短的链表需要荣光补 0 来实现  
 */  
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {  
    // 考虑两个链表为空的情况  
    if (null == l1 || null == l2) {  
        return null == l1 ? l2 : l1;  
    }  
  
    // 定义负数做头结点的链表ListNode, 用于存储结果  
    ListNode result = new ListNode(-1);  
    // 定义当前链表的指针  
    ListNode current = result;  
    // 定义进位  
    int increase = 0;  
    // 遍历两个链表, 如果两个链表都为空, 并且进位为 0, 则结束循环  
    // 例如 l1 = [2, 3, 6], l2 = [5, 6, 4] 时, 当 l1, l2 都遍历完毕后, 还需要判断进位, 此时进位为 1, 则需要再增加一个节点, 最终结果为 [7, 9, 0, 1]    while (l1 != null || l2 != null || increase != 0) {  
        // 计算两个链表的值, 如果链表为空, 则补充为 0        /*         * 例如 l1 = [2, 3, 6], l2 = [5, 6, 4, 9, 11] 时, 当 l2 遍历到 9 时, l1 已经为空了,  
         * 此时需要给 l1 补充一个 0, 才能继续计算, 此时 l1.val = 0, l2.val = 9, increase = 1         */        int sum = (null == l1 ? 0 : l1.val) + (null == l2 ? 0 : l2.val) + increase;  
        current.next = new ListNode(sum % 10);  
        // 计算进位  
        increase = sum / 10;  
        // 移动链表ListNode l1 和 l2 的指针, 用于下一次计算  
        if (l1 != null) {  
            l1 = l1.next;  
        }  
        if (l2 != null) {  
            l2 = l2.next;  
        }  
        // 移动链表的指针, 用于下一次计算  
        current = current.next;  
    }  
    // 返回链表的下一个节点, 因为第一个节点是负数做头结点的链表ListNode  
    return result.next;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37