题目简述
题目链接: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;
}
};
声明:
本文采用
BY-NC-SA
协议进行授权,如无注明均为原创,转载请注明转自
SigmaPoet
本文地址: 【力扣题解】2.两数相加
本文地址: 【力扣题解】2.两数相加