题目简述

题目链接：https://leetcode.cn/problems/add-two-numbers/

简述：用链表实现大整数加法

题解

大整数加法

就是一个大整数加法，注意满十进一。两个N位数相加，和最大是N+1位数。

时空复杂度都是O(n)。

结构体数组指针

这里还是要注意一下的，平时不怎么用指针，要被指针搞死了。

注意在C++中创建指针时，计算机将分配用来存储地址的内存，但不会分配用来存储指针所指向的数据的内存。所以指针定义完了一定要初始化。

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}  //默认无参数的初始化函数
}

int main() {
    struct ListNode* ptrNode = new ListNode();  //使用new来动态为指针分配内存
    //new 将找到一个长度正确的内存块，并返回该内存块的地址。
    //程序员要做的就是将该地址赋值给一个指针

    //使用完成后，用delete释放
    delete ptrNode;
}

因为题目中是将算法写在一个返回ListNode*类型的成员函数中，供外部调用，所以不能在返回前把指针删除了。不知道这样会不会导致内存泄漏问题。

代码

• 代码链接：https://gitee.com/sigmapoet/myleetcode/tree/master/1-100/2.%E4%B8%A4%E6%95%B0%E7%9B%B8%E5%8A%A0

class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { 
            struct ListNode* answer = new ListNode();
            struct ListNode* head = answer;
            struct ListNode* orgl1 = l1;
            struct ListNode* orgl2 = l2;
            int curPos = 0;
            int len1 = 1, len2 = 1;
            int maxLen;
            int fullTen = 0;

            while(l1->next != nullptr) {
                l1 = l1->next;
                len1 ++;
            }
            while(l2->next != nullptr) {
                l2 = l2->next;
                len2 ++;
            }
            //when sumbit to leetcode, maxLen = max(len1, len2)
            //this is because the differences between my l1,l2 and leetcode's
            maxLen = max(len1, len2)-1;
            for(int i = 0; i < maxLen; ++ i) {
                int val1 = 0, val2 = 0;
                if(i < len1) {
                    val1 = orgl1->val;
                    orgl1 = orgl1->next;
                }
                if(i < len2) {
                    val2 = orgl2->val;
                    orgl2 = orgl2->next;
                }

                answer->val = (val1 + val2 + fullTen) % 10;
                fullTen = (val1 + val2 + fullTen) / 10;
                if(i == maxLen - 1) {
                    if(fullTen) {
                        answer->next = new ListNode();
                        answer = answer->next;
                        answer->val = fullTen;
                        answer->next = nullptr;
                    }
                    else {
                        answer->next = nullptr;
                    }
                }
                else {
                    answer->next = new ListNode();
                    answer = answer->next;
                }
            }
            return head;
        }
};