EasyLeetCode02，两数相加
题意
题意很简单，给定两个非空的链表。用逆序的链表来表示一个整数，要求我们将这两个数相加，并且返回一个同样形式的链表。
除了数字0之外，这两个数都不会以0开头，也就是没有前导0。
所谓的逆序的链表，题目中给了示例，也就是下面这种形式：
比如2 -> 4 -> 3，存的是342，并不是243，这里需要注意。
数据范围
每个链表中的节点数在范围
[1, 100]内0 <= Node.val <= 9题目数据保证列表表示的数字不含前导零
解法
题目本身很简单，困难的点在于链表的使用。
我们知道，在C++当中有指针的概念，指针可以指向一个变量的内存地址。通过使用指针，我们可以设计一种特殊的数据结构，让某一个结构体当中存储一个指向同样类型结构体的指针。这样的话，我们就可以通过结构体当中的指针，把若干个结构体的实例连接起来，就像是一个链条一样，这种数据结构叫做链表。
我们可以来看下题目给定的链表的定义：
之前有同学问过我，你用的这个结构体哪来的，也没看到你定义。其实这是很多OJ的特点，我们需要实现的只是核心逻辑，有时候是写一个函数，有时候是写一个类。除了我们编写的代码之外，裁判机还会运行很多其他的逻辑。只不过这些逻辑和我们的问题没有关系，所以全部隐藏了。
比如这里链表的定义，LeetCode已经替我们定义好了。我们只需要用就行了，至于它定义在哪里，我们并不需要关心。
我们来看下这个结构体，它的名字叫ListNode，顾名思义表示的是链表的节点。它当中有两个成员变量，一个是int型的val，还有一个是ListNode指针。这里的val存储的是一个0-9的整数，表示某一个整数的其中一位，这里的指针自然是用来指向下一个节点的。
我们再来看下我们要实现的函数：
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 复制代码
传入的参数有两个，分别是两个链表的头指针，要返回的结果也是一个指针。是我们生成的新链表的头指针。
所以我们要做的事情有两个，一个是遍历l1和l2这两个链表，第二个是把其中的数相加，生成一个新的链表，返回个新的链表的头指针。
链表不像数组，我们无法知道确定的长度，只能使用while循环来遍历，从头结点一位一位移动，当遍历到空指针时停止。在这题里我们需要遍历两个链表，所以循环条件应该这么写：
while (l1 != nullptr || l2 != nullptr) { // todo } 复制代码遍历链表之后， 剩下的就简单了，就是完成一个加法。到这个时候，我们会发现链表逆序存储是非常有好处的。因为我们拿到的每一个元素它的位置是确定的，第一个拿到的一定是个位，第二个拿到的是十位。如果我们链表是正序存储，我们在知道链表长度之前，是不知道第一位到底是哪一位的。
所以表面上看逆序存储的链表好像有点麻烦，其实是替我们简化了问题。
最后，我们只需要注意一下加法的进位， 很容易写出代码：
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* ret = new ListNode(); ListNode* pnt = ret; bool carry = false; while (l1 != nullptr || l2 != nullptr || carry) { int cur = 0; if (l1 != nullptr) { cur += l1->val; l1 = l1->next; } if (l2 != nullptr) { cur += l2->val; l2 = l2->next; } if (carry) { cur ++; } if (cur >= 10) { cur -= 10; carry = true; }else { carry = false; } pnt->next = new ListNode(cur); pnt = pnt->next; } return ret->next; } }; 复制代码关于进位的处理没什么好说的，唯一要注意一下的就是while循环当中的条件，多了一个是否进位的判断。这是对最高位发生进位时的处理，否则会导致最高位的进位丢失。
只要注意到这个trick，并且了解链表基本的使用，这道题也就迎刃而解了，是不是很简单呢？
好了，关于这题就聊到这里，感谢大家的阅读。
作者：程序员老梁
链接：https://juejin.cn/post/7027651377216094239