LeetCode-Hot100-两数相加

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

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

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

示例 1：

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

输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
1
2
3
4
5
6
7
8
9
10
11

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/add-two-numbers

这题考的不难，但是对于没怎么写过链表的就有点无从下手了， 学过链表的都知道，链表是一个节点通过指针指向下一个节点的，做到随机存储，顺序读取。（因为链表是不同地址的数通过指针联系起来的，链表读取得通过指针顺序地一个个找到你想要的节点读取）
而本题是一个简单的两链表相加结果数据存储在一个新的链表。这个题在数据结构学链表的时候老师就举过两个，一个是两链表相加结果存储在其中一个链表，一个就是本题。不过本题要求加一个进位的机制，因为每一个节点的数可能 > 10。
纰漏：是怎么去返回一个新的链表，因为在给新链表的赋值的时候索引会一直往后跑的，最后写完了，索引也跑到最后一个节点里了，这不能返回整个链表。
解决方法：链表一般都会有一个头结点，这个节点一般不存储数值，起到一个标记链表起始的作用。
这里再加深记忆一下在c++里建立快速一个链表的代码

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) {} // 节点数据域赋值并指定下一个节点的方法
 };
1
2
3
4
5
6
7
8
9

这题虽然写的时间挺长，但是提交第二次就过了，成绩也不错超过了99%的

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* index1 = l1; // 链表l1的索引节点1，用来遍历链表
        ListNode* index2 = l2; // 链表l2的索引节点2
        ListNode* head = new ListNode(); // 创建头结点，不存储数据，用来标记链表开头节点
        ListNode* index3 = head; // 新链表的索引节点3
        head -> next = index3;   // 让索引3指向头结点的下一个节点，也就是正式开始存储数据的节点
        int upcode = 0,mid = 0;  // 设置进位数默认为0，和中间数暂存每个节点相加的数据
        while(index1 != nullptr || index2 != nullptr) { // 如果链表1或者链表2没遍历完的话加上每个节点的数值
            if (index1 == nullptr) { // 如果链表1遍历完了，但是链表2没遍历完，仍要加上链表2的数据并且继续遍历链表2
                mid = (index2 -> val) + upcode; //这里的mid要加上每次进位的数
                index2 = index2 -> next; //index2向后移
            } else if (index2 == nullptr) { // 逻辑同上
                mid = (index1 -> val) + upcode;
                index1 = index1 -> next;
            } else { // 其他情况就是（index1 != nullptr && index2 != nullptr）
                mid = (index1 -> val) + (index2 -> val) + upcode;
                index1 = index1 -> next;
                index2 = index2 -> next;
            }
            if( mid >= 10 ) { // 如果每一次相加的结果大于10，我们取一下要进位的数和个位数
                upcode = mid / 10;
                mid = mid % 10;
            } else { // 否则就重置一下进位数为0 
                upcode = 0;
            }
            index3 -> next = new ListNode(mid); // 存一下结果的个位数
            index3 = index3 -> next; // index3向后移一位
        }
        if (upcode != 0 ) index3 -> next = new ListNode(upcode); // 这里要注意最后一次循环结束后还有一个进位数没处理，要判断一下此进位数是否为0，不为零再给他新建一个节点，index3不要移动了，因为已经到了最后一个节点了。
        return head -> 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