一、前言

最近心血来潮做了两三道LeetCode算法题，发现是真的太难，也许是因为自己以前没有接触过算法相关，所以这些基础算法都是现学现卖，写此篇文章也是为了记录一下自己的经验。

二、正文

先上题目和代码：

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

1
2
3
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
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
#include <iostream>
using namespace std;
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};
class Solution
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        ListNode *head = new ListNode(-1);//两数之和的头节点
        ListNode *move = head;//移动节点
        int sum = 0;
        bool carry = false;
        while (l1 != nullptr || l2 != nullptr)
        {
            sum = 0;
            if (l1 != nullptr)
            {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2 != nullptr)
            {
                sum += l2->val;
                l2 = l2->next;
            }
            if (carry)
                sum++;
            move->next = new ListNode(sum % 10);
            move = move->next;
            carry = sum >= 10 ? true : false;
        }
        if (carry)
        {
            move->next = new ListNode(1);
        }
        return head->next;
    }
};

先捋一下思路，题目要求用链表结构去存储每一位数，再把两个数相加，还要考虑是否进位，不妨可以把两个链表抽象为两条线，每个节点相当于线上的结点，分别遍历两条线，并将对应节点相加后存入新链表

思路如下

三、总结

难度不大，思路也比较简单，只要理解链表的结构就可以很轻松的写出代码，同时这道题也可以当作链表的参考，囊括了链表的构造和读取。虽然这样解决了问题，但是程序的效率不高，后续有思路了会优化一下，并添加链表的删除与增加节点的操作。