题解 | #链表之和#

题目描述：给定两个代表非负数的链表，数字在链表中是反向存储的（链表头结点处的数字是个位数，第二个结点上的数字是十位数...），求这个两个数的和，结果也用链表表示。
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出： 7 -> 0 -> 8
示例1：
        输入：{0},{0}
        返回值：{0}
示例2：
        输入：{0},{1}
        返回值：{1}
思路：由于链表中数字为反向存储，靠考虑直接从两个链表的第一个数字相加作为一个节点添加到新链表中，若和大于10，则取余数作为节点值，取除数作为下一个节点值和的分量计算，若和小于10，则取和作为节点值即可；直到一个链表为空；之后再分别遍历两个链表，若链表不为空继续将对应节点添加到新链表中即可。具体代码如下：

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        // write code here 写的是数字在链表中正向存储的情况
//         if(l1 != NULL && l2 != NULL)
//         {
//             vector<int> r,r1,r2;
//             ListNode *p=l1,*q=l2;
//             while(p!= NULL)
//             {
//                 r1.push_back(p->val);
//                 p = p->next;
//             }
//             while(q!= NULL)
//             {
//                 r2.push_back(q->val);
//                 q = q->next;
//             }
//             delete p;
//             delete q;
//             int n1 = r1.size()-1,n2 = r2.size()-1,temp=0;
//             while(n1>=0 && n2>=0)
//             {
//                 int p1 = r1[n1],p2=r2[n2],p = (p1+p2+temp),mod=p%10,temp = p/10;
//                 r.push_back(mod);
//                 n1--;n2--;
//             }
//             while(n1 >= 0)
//             {
//                 int p1 = r1[n1],p = (p1+temp),mod=p%10,temp = p/10;
//                 r.push_back(mod);
//                 n1--;
//             }
//             while(n2 >= 0)
//             {
//                 int p2=r2[n2],p = (p2+temp),mod=p%10,temp = p/10;
//                 r.push_back(mod);
//                 n2--;
//             }
//             if(temp != 0)
//                 r.push_back(temp);
//             int n = r.size();
//             for(int i=0;i<n/2;i++)
//             {
//                 int temp = r[i];
//                 r[i] = r[n-i-1];
//                 r[n-i-1] = temp;
//             }
//             ListNode* res = (ListNode *)malloc(sizeof(ListNode));
//             p = res;
//             for(int i=0;i<n;i++)
//             {
//                 ListNode *q1 = (ListNode *)malloc(sizeof(ListNode));
//                 q1->val = r[i];
//                 q1->next = p->next;
//                 p->next = q1;
//                 p = p->next;
//             }
//             return res->next;
//         }
//         return NULL;
        if(l1 != NULL && l2 != NULL)
        {
            vector<int> r,r1,r2;
            ListNode *p=l1,*q=l2;
            while(p!= NULL)
            {
                r1.push_back(p->val);
                p = p->next;
            }
            while(q!= NULL)
            {
                r2.push_back(q->val);
                q = q->next;
            }
            delete p;
            delete q;
            int n1 = r1.size()-1,n2 = r2.size()-1,i=0,j=0,temp=0;
            while(i<=n1 && j<=n2)
            {
                int p1 = r1[i],p2=r2[j],p = (p1+p2+temp),mod=p%10;
                if(p >= 10)
                {
                    r.push_back(mod);
                }
                else
                    r.push_back(p);
                temp = p/10;
                i++;j++;
            }
            while(i<=n1)
            {
                int p1 = r1[i],p = (p1+temp),mod=p%10;
                if(p >= 10)
                {
                    r.push_back(mod);
                }
                else
                    r.push_back(p);
                temp = p/10;
                i++;
            }
            while(j<=n2)
            {
                int p2=r2[j],p = (p2+temp),mod=p%10;
                if(p >= 10)
                {
                    r.push_back(mod);
                }
                else
                    r.push_back(p);
                temp = p/10;
                j++;
            }
            if(temp != 0)
                r.push_back(temp);
            int n = r.size();
            ListNode* res = (ListNode *)malloc(sizeof(ListNode));
            p = res;
            for(int i=0;i<n;i++)
            {
                ListNode *q1 = (ListNode *)malloc(sizeof(ListNode));
                q1->val = r[i];
                q1->next = p->next;
                p->next = q1;
                p = p->next;
            }
            return res->next;
        }
        return NULL;
    }
};