leecode2:两数相加

1.题目描述:

　　给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

2.示例

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807

3.解析

（1）此题难度不大，记录此题是想记录一个思路。在计算两数之和时，由于加法进位仅可能使得两个加数中最长的加数进位。所以使用链表表示加法时，逆序排列加数，可以有很好的扩展性，无需进行移动。

由此可想，在一些单方向扩展的数据结构中使用链表，可以避免移动数据。

（2）另外此题，编写后总结如下问题：

　　<1>十进制加法中，两数之和的进位值最大为1：先考虑低位可能产生的最大进位值情况：9+9=18，最大进位值是1.在其高一位上，可能产生的最大进位且本位最高的仍为：9+9=18.由于8+1<10，故不会产生进位。从而得出结论。

　　<2>另外注意，进位至位数超过两加数的最大位数时，对最高位的处理。

4.最后给出代码

/**
 * 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) {

        bool carryMark = false; //进位符
        struct ListNode* lastNode = nullptr;  //存储上一个结点
        struct ListNode* head = nullptr;    //存储首结点
        while(l1!=nullptr||l2!=nullptr||carryMark){
            int currentBitValue = 0;
            if(carryMark){
                currentBitValue +=1;
            }
            if(l1!=nullptr&&l2!=nullptr){
                currentBitValue =currentBitValue+ (l1->val)+(l2->val);
                l1 = l1->next;
                l2 = l2->next;
            }
            else if(l1!=nullptr){
                currentBitValue =currentBitValue + (l1->val);
                l1 = l1->next;
            }
            else if(l2!=nullptr){
                currentBitValue =currentBitValue + (l2->val);
                l2 = l2->next;
            }
            else{
                //最高位进位为1
            }
            if(currentBitValue>=10){
                currentBitValue =currentBitValue %10;
                carryMark = true;
            }else{
                carryMark = false;
            }
            struct ListNode* currentNode = new struct ListNode(currentBitValue);
            if(lastNode==nullptr){//如果上一个结点为空，则证明是第一个结点和。
                head = currentNode;
            }else{
                lastNode->next=currentNode;
            }
            lastNode = currentNode;
        }
        return head;
    }
};