老卫带你学---leetcode刷题(2.Add Two Numbles)

问题：

您将获得两个非空链表，表示两个非负整数。数字以相反的顺序存储，每个节点包含一个数字。添加两个数字并将其作为链接列表返回。
您可以假设这两个数字不包含任何前导零，除了数字0本身

示例：

输入：（2  - > 4  - > 3）+（5  - > 6  - > 4）
输出： 7  - > 0  - > 8
说明： 342 + 465 = 807。

解决：

思想：

使用变量跟踪进位并从列表头部开始模拟逐位数字，其中包含最低有效数字。
就像你在一张纸上总结两个数字一样，我们首先将最低有效数字相加，即 L1与L2。但每个节点里的数是0-9，那么相加起来以后，我们就需要考虑其进位情况。例如5+7=12这样。

伪代码：

• 初始化返回节点L
• 初始化进位carry=1
• 初始化L1与L2的头节点p与q
• 循环如下步骤，直到L1与L2到达尽头：

1. 设置L1的头节点p的值为x。如果p为终点，则设为0
2. 设置L2的头节点q的值为y。如果q为终点，则设为0
3. 设置sum=x+y+carry
4. 更新carry=sum/10
5. 让L的next节点为sum%10
6. 判断是否L1与L2到达终点
7. 回到第1步

代码

c++代码:

/**
 * 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) {
        return addBybit(l1,l2,0);
    }
    ListNode* addBybit(ListNode* l1,ListNode* l2,int carry){
        if(l1==NULL)
            l1=new ListNode(0);
        if(l2==NULL)
            l2=new ListNode(0);
        ListNode* l=new ListNode((l1->val+l2->val+carry)%10);
        carry=(l1->val+l2->val+carry)/10;
        if(l1->next != NULL || l2->next!=NULL || carry==1){
            l->next=addBybit(l1->next,l2->next,carry);
        }
    return l;
    }
};