Leetcode 第二题：Add Two Numbers（c++实现）

Leetcode

c++

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

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

解决思路：从表头开始相加，记录每次相加的进位。

具体算法：伪代码如下：初始化进位变量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的新节点附加到返回列表中。

时间空间复杂度：时间复杂度：O（max（m，n））。 假设m和n分别表示l1和l2的长度，上面的算法最多迭代max（m，n）次。空间复杂度：O（max（m，n））。 新列表的长度最多为max（m，n）+1。

提供本文打败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;    }};