Leetcode 第二题：Add Two Numbers（c++实现）
1、问题描述：
您将获得两个非空链表，表示两个非负整数。 数字以相反的顺序存储，每个节点包含一个数字。 添加两个数字并将其作为链接列表返回。
您可以假设这两个数字不包含任何前导零，除了数字0本身。
2、问题示例：
输入：（2 - > 4 - > 3）+（5 - > 6 - > 4）
输出：7 - > 0 - > 8
说明：342 + 465 = 807。
3、输入与输出：
/**
* 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) {
}
};
4、解决思路：
从表头开始相加，记录每次相加的进位。
5、具体算法：
伪代码如下：
初始化进位变量carry=0
将p和q分别初始化为l1和l2的头部。
循环遍历列表l1和l2，直到达到两端。
将x设置为节点p的值。如果p已达到l1的末尾，则设置为0。
将y设置为节点q的值。如果q已达到l2的末尾，则设置为0。
设置sum = x + y + carry。
更新carry = sum / 10。
使用（sum mod 10）的值创建一个新节点，并将其设置为当前节点的下 一个节点，然后将当前节点前进到下一个节点。
推进p和q。
检查carry = 1，如果是，则将带有数字11的新节点附加到返回列表中。
6、时间空间复杂度：
时间复杂度：O（max（m，n））。 假设m和n分别表示l1和l2的长度，上面的算法最多迭代max（m，n）次。空间复杂度：O（max（m，n））。 新列表的长度最多为max（m，n）+1。
7、提供本文打败90%人的代码：
**
* 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) {
struct ListNode * node= new struct ListNode(0) ;
struct ListNode *p=l1,*q=l2,*root=node;
int carry=0;
while (p!=NULL || q!= NULL)
{
int x=(p==NULL)?0:p->val;
int y=(q==NULL)?0:q->val;
int result=x+y +carry;
carry=result/10;
node->next= new struct ListNode (result %10);
node =node->next;
if (p!=NULL) p=p->next;
if (q!=NULL) q=q->next;
}
if (carry>0)
node->next=new struct ListNode(carry);
return root->next;
}
};
