力扣算法题Day2

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

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

4b625b8fa9f840762f6bdc8e46bf1e37

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

示例 2：

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

示例 3：

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

提示：

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

解题思路：

首先数字是由链表逆序存储，那遍历这个链表的时候就是从最后一位开始遍历，这和我们一样我们计算两数相加计算时也是从最后一位开始。

相加时分两种情况：等长和不等长。

等长时两个数获取位次的次数也就是next的次数是一样的。

不等长时一个数位次获取完之后就停止获取下一位。另一个数继续获取下一位。

总结下来就是循环看数字还有没有下一位。

1
2
3
4
5
6
7
8
while (p || q) {
	if (p) {
        p = p->next;
    }
    if (q) {
        q = q->next;
	}
}

那我们就先把两个数字的最后一位相加，如果

19>两数之和>9，

那么有进位1，两数之和肯定大于等于10或者小于等于18，如果两数之和<10，那么没有进位或可以当成进位0，

进位可以直接让两数之和/10获得进位（C++中/运算符的特性），当前位余数为两数之和%10

进位需要在下一位运算时加上，后面的位次循环。

最后一位相加时如果有进位需要单独开一个节点存储进位1。

那么进位是从刚开始到最后都是需要的，可以初始化为0。

那么我们可以用下面的代码来表示上面的逻辑。

代码：

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
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *p = l1, *q = l2;
        ListNode *l = nullptr, *r = l; // l代表第一个结点。
        int t = 0;//初始化进位
        while (p || q) { // 判断是否两个数是否遍历完毕
            if (p) {     // 遍历l1
                t +=
                    p->val; // 进位为1或者0，每次计算同位次之和直接加上进位就可以
                p = p->next; // 指向下一位次
            }
            if (q) { // 遍历l2
                t +=
                    q->val; // 进位为1或者0，每次计算同位次之和直接加上进位就可以
                q = q->next; // 指向下一位次
            }
            // 经过上面的过程当前位次和计算完毕

            // 接下来创建结点存储数值
            if (!l) {
                l = r = new ListNode(
                    t % 10); // l为null，代表要创建第一个节点，同时让l = r
            } else {
                r->next = new ListNode(t % 10); // 尾插法循环插入
                r = r->next;
            }
            // 最后获得进位
            t /= 10;
        }
        // 如果最后还有进位那么再创建一个结点存储进位
        if (t) {
            r->next = new ListNode(t);
        }
        return l; // 返回第一个结点
    }
};