LeetCode题解(2)-- Add Two Numbers

原题：　　　　　　　　https://leetcode.com/problems/add-two-numbers/

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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

通过单链表模拟大整数加法。看错题好几次，开始想复杂了，以为是高位数字是链表头部。

核心算法主要是尾插法建新链表，需要注意两个数位数不同的情况（三个while）和怎么满十进一（通过一个flag），最后表头的空节点还要T掉。

我的ac代码，复杂度O（m+n）：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
12         ListNode *p=new ListNode(0);  
13         ListNode *l3=new ListNode(0);
14         ListNode *en=l3;
15         int flag=0;
16         while(l1!= NULL && l2!= NULL){
17             p=new ListNode(0);
18             p->val=(l1->val + l2->val +flag) %10;
19             if((l1->val + l2->val+flag) >=10)
20                 flag=1;
21             else
22                 flag=0;
23             en->next=p;
24             en=en->next;
25             l1=l1->next;
26             l2=l2->next;
27         }
28         while(l1!= NULL){
29             p=new ListNode(0);
30             p->val=(l1->val+flag)%10;
31             if((l1->val+flag) >= 10)
32                 flag=1;
33             else
34                 flag=0;
35             en->next=p;
36             en=en->next;
37             l1=l1->next;
38         }
39         while(l2!= NULL){
40             p=new ListNode(0);
41             p->val=(l2->val+flag)%10;
42             if((l2->val+flag) >= 10)
43                 flag=1;
44             else
45                 flag=0;
46             en->next=p;
47             en=en->next;
48             l2=l2->next;
49         }
50         if(flag==1){                           //这一段可简化为 en->next=new ListNode(1);
51             p=new ListNode(0);
52             p->val=1;
53             en->next=p;
54             en=en->next;
55         }
56         l3=l3->next;    
57         return l3;
58     }
59 };

LeetCode题解(2)-- Add Two Numbers

原题： https://leetcode.com/problems/add-two-numbers/

原题：　　　　　　　　https://leetcode.com/problems/add-two-numbers/