LeetCode【0002】两数相加(已搞懂,未练习)"/>
探索LeetCode【0002】两数相加(已搞懂,未练习)
目录
- 0、题目
- 1、官方答案(ok)
- 注1
- 注2
- 2、第二个参考答案(ok)
- 2.1 思路一
- 注3
- 2.2 思路二
- 注4
0、题目
题目链接:【0002】两数相加
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 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, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
1、官方答案(ok)
官方答案
代码1
/*** Definition for singly-linked list.* 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) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode *head = nullptr, *tail = nullptr; // 分别指向什么?head和tail分别干啥?int carry = 0;while (l1 || l2) {int n1 = l1 ? l1->val: 0; // 此处没看懂,搜索语法效果不佳int n2 = l2 ? l2->val: 0; // 此处没看懂,搜索语法效果不佳 int sum = n1 + n2 + carry;if (!head) {//相加和的个位放在新的结点,但是为什么跟head、tial有关?head、tial用来指什么?head = tail = new ListNode(sum % 10); } else {tail->next = new ListNode(sum % 10); //相加和的个位放在新的结点,但是为什么跟tial有关?tail = tail->next;}carry = sum / 10;if (l1) {l1 = l1->next;}if (l2) {l2 = l2->next;}}if (carry > 0) { // 考虑的是最后一位相加之后,是否需要进位tail->next = new ListNode(carry);}return head;}
};
注1
找到一些关于?用法的示例:x < 0 ? y = 10 : z = 20;
这个语句被称为条件表达式,它由 3 个子表达式组成,使用问号 ? 和冒号 : 分隔。这 3 个表达式分别是:x<0,y = 10 和 z = 20。上面的条件表达式与以下 if-else 语句执行相同的操作:
if (x < 0)y = 10;
elsez = 20;
根据以上定义,那么以下代码
int n1 = l1 ? l1->val: 0;
int n2 = l2 ? l2->val: 0;
202303116
其意思是否为:
如果n1=l1,那么应该是什么的值设置为l1的值?如果n1!=l1,那么应该是什么的值设置为0?
如果n2=l2,那么应该是什么的值设置为l2的值?如果n2!=l2,那么应该是什么的值设置为0?
感觉不对劲…
20230317
回头看,感觉意味着:如果l1存在,那么将l1的值赋给n1;如果l1不存在,那么将0赋给n1!
注2
20230318
除此之外,还有一个比较大的问题是以下代码
if (!head) {//相加和的个位放在新的结点,但是为什么跟head、tial有关?head、tial用来指什么?head = tail = new ListNode(sum % 10); } else {tail->next = new ListNode(sum % 10); //相加和的个位放在新的结点,但是为什么跟tial有关?tail = tail->next;
}
20230319
head应该代表的是输出链表的链首,tail代表的是输出链表的链尾。
在没有该链表和链首的情况下,需要同时给出链表和链首。
随后只需要更新链尾的数据即可,最后返还的是链首。
2、第二个参考答案(ok)
答案链接
2.1 思路一
将长度较短的链表在末尾补零使得两个连表长度相等,再一个一个元素对其相加(考虑进位)
- 获取两个链表所对应的长度
- 在较短的链表末尾补零
- 对齐相加考虑进位
代码2
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {int len1=1;//记录l1的长度int len2=1;//记录l2的长度ListNode* p=l1;ListNode* q=l2;while(p->next!=NULL)//获取l1的长度{len1++;p=p->next;}while(q->next!=NULL)//获取l2的长度{len2++;q=q->next;}if(len1>len2)//l1较长,在l2末尾补零{for(int i=1;i<=len1-len2;i++){q->next=new ListNode(0);q=q->next;}}else//l2较长,在l1末尾补零{for(int i=1;i<=len2-len1;i++){p->next=new ListNode(0);p=p->next;}}p=l1; // 何必又来定义一次?q=l2; // 何必又来定义一次?bool count=false;//记录进位ListNode* l3=new ListNode(-1);//存放结果的链表ListNode* w=l3;//l3的移动指针 // 是否多此一举?int i=0;//记录相加结果while(p!=NULL&&q!=NULL){// 沙比,前面的count是bool型...此处何解?// 难道true可以当作数值1来进行加减运算?// count+(p->val)+(q->val)???是用来计算进位的吧i=count+p->val+q->val;w->next=new ListNode(i%10);count=i>=10?true:false;w=w->next;p=p->next;q=q->next;}if(count)//若最后还有进位{w->next=new ListNode(1);w=w->next;}return l3->next; }
};
注3
20230317
针对以上代码,主要是对代码末尾的bool类型参数count参加int类型的加法运算感到困惑?!
20230319
在Microsoft visual studio中进行测试:
int a = 1;bool b = true;cout << "a+b=" << a + b;
输出结果为
a+b=2
a+c=1
至此我也不必纠结了,掌握这个规则即可:
bool类型的参数可以参加整数型加法运算,true时值为1,false时值为0
2.2 思路二
不对齐补零,若链表不为空则用 sum(代表每个位的和的结果)加上,考虑进位。
代码3
/*** Definition for singly-linked list.* 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) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* head=new ListNode(-1);//存放结果的链表ListNode* h=head;//移动指针 // 多一个h指针我是不懂的int sum=0;//每个位的加和结果bool carry=false;//进位标志while(l1!=NULL||l2!=NULL){sum=0;if(l1!=NULL){sum+=l1->val;l1=l1->next;}if(l2!=NULL){sum+=l2->val;l2=l2->next;}if(carry)sum++;h->next=new ListNode(sum%10);h=h->next;carry=sum>=10?true:false;}if(carry){h->next=new ListNode(1);}return head->next;}
};
注4
20230317
唯一没有搞懂为什么最后返还的是return head->next;
? h和head之间到底是什么关系?
20230319
代码3中的h即为代码1中的tail,用来持续更新相加和。
代码3中返回的head->next
不同于代码1中返回的head
是因为,代码3中链表的第一位是-1
。
此为最后一个细节问题,为什么链表首位是-1
?搜索后无果,以后回过头再试解答之。
20230320
权威解答:
值为-1的节点是附加头节点,如果没有这个节点的话,插入个位的时候它会有不同的代码,那个写法就会稍微复杂一点,有了这个节点,就一个循环就搞定了,所以它最后返回的时候是返回head->next节点,就把这个附加头节点给跳过去了,也就是说,外面拿到的是不带这个-1的这个节点的是整个相加的结果。
更多推荐
探索LeetCode【0002】两数相加(已搞懂,未练习)
发布评论