链表-2.两数相加-力扣(LeetCode)
一、题目解析
1、对逆序存储的数字求和，返回一个同样逆序的链表
2、不会出现先导0的情况
二、算法原理
解法：模拟两数相加的过程
定义一个变量t记录每一位之和，按照两数相加的过程，t=2+5，new 一个ListNode(t%10)，这里7%10=7，t/=10进位操作，然后继续进行下去
哨兵位头节点和tail节点
为了避免边界条件的判断和操作遍历，我们会创建一个newhead的哨兵位头节点，该节点并不存储任何有限数据，仅做哨兵标记处理；由于返回逆序结果，我们需要多次对链表进行尾插操作，所以我们定义tail节点用于标记链表中最后一个节点，节约从头遍历找尾的时间
遍历边界条件
由于无法保证两个链表长度一致，所以会出现一个链表遍历完了，但另一个却没有遍历完的情况，需要特殊处理
检查记录每位之和变量t
存在两个链表都遍历完了，但是由于循环条件的设置，导致t中的进位情况没有处理完，所以需要在返回结果之前，检查t是否未0，不未0则需要new ListNode(t)，然后接到tail节点的后面，最终返回newhead->next即可，我们返回的逆序和链表不包括哨兵位头节点
对于链表操作模糊的读者可以移步博主的另一篇博客
数据结构之单链表-CSDN博客or带头双向循环单链表-CSDN博客
三、代码示例
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2){ListNode* newhead = new ListNode();ListNode* tail = newhead; ListNode* cur1 = l1;ListNode* cur2 = l2;int t = 0;while(cur1!=nullptr||cur2!=nullptr){if(cur1 == nullptr){t+=cur2->val;cur2 = cur2->next;}else if(cur2 == nullptr){t+=cur1->val;cur1 = cur1->next;}else{t+=cur1->val;t+=cur2->val;cur1=cur1->next;cur2=cur2->next;}ListNode* newnode = new ListNode(t%10);t/=10;tail->next = newnode;tail=tail->next;}if(t!=0){ListNode* newnode = new ListNode(t);tail->next = newnode;}return newhead->next; }
};