Add Two Num

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
给定两个表示两个非负的链表。数字以逆序存储，每个节点包含一个数字。将两个数字相加，以链表形式返回和。
Example：
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

解：

intuition（直觉）

Figure 1.342 + 465 = 807相加的图示

算法：

和我们自己在纸上做加法类比，下面是pseudocode（伪代码）。

• 初始化返回链表的当前结点为虚设头节点
• 初始化进位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%10，设为当前结点的下一节点，前进到下一节点。
  p,q都前进下一节点。
• 检查carry是否为1，为1，则添加新的值为1的节点到返回列表。
• 返回虚设头的下一节点。
  注意一下情形：

Test case	Explanation
l1=[0,1] l2=[0,1,2]	当一个链表比另一个长
l1=[] l2=[0,1]	一个链表为空
l1=[9,9] l2=[1]	结尾有进位

代码如下(C++)：
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int carry =0; ListNode *p=l1, *q=l2, *curr = new ListNode(0); ListNode *dummyhead=curr; while(1){ int x = (p!=NULL)?p->val:0; int y = (q!=NULL)?q->val:0; int sum = x+y+carry; carry = sum/10; curr->val = sum%10; if(p!=NULL) p=p->next; if(q!=NULL) q=q->next; if(p||q){ curr->next = new ListNode(0); curr=curr->next; }else{ if(carry){ curr->next = new ListNode(0); curr=curr->next; } break; } } if(carry>0){ curr->val= carry; } return dummyhead; }
因为c++采用指针创建链表，在判断结束条件的时候要考虑创建next节点的条件。

复杂度：

时间复杂度：O(max(m,n))
空间复杂度：O(max(m,n)),最大为max(m,n)+1,用来存储结果链表。