[leetcode] Add Two Numbers *

 1 /*
 2  * Easy
 3  *
 4  * @author: HZT
 5  * @date: 2013-3-7
 6  */
 7 
 8 #include <iostream>
 9 using namespace std;
10 
11 struct ListNode{
12     int val;
13     ListNode *next;
14     ListNode(int x) : val(x), next(NULL) {}
15 };
16 
17 class Solution {
18 public:
19     ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
20         // Start typing your C/C++ solution below
21         // DO NOT write int main() function
22         if(!l1) return l2;
23         if(!l2) return l1;
24 
25         ListNode* ans = NULL;
26         ListNode* tail = new ListNode(0);
27         int carry = 0;
28 
29         while(true){
30             int val = (l1->val + l2->val + carry) % 10;
31             carry = (l1->val + l2->val + carry) / 10;
32 
33             tail->next = new ListNode(val);
34             tail = tail->next;
35             if(!ans) ans = tail;
36 
37             l1 = l1->next;
38             l2 = l2->next;
39 
40             if(!l1 || !l2){
41                 if(!l2) l2 = l1;
42                 while(l2){
43                     int val = (l2->val + carry) % 10;
44                     carry = (l2->val + carry) / 10;
45 
46                     tail->next = new ListNode(val);
47                     tail = tail->next;
48                     if(!ans) ans = tail;
49 
50                     l2 = l2->next;
51                 }
52 
53                 if(carry){
54                     tail->next = new ListNode(carry);
55                     tail = tail->next;
56                     if(!ans) ans = tail;
57                 }
58 
59                 break;
60             }
61         }
62 
63         return ans;
64     }
65 };
66 
67 int main(){
68     Solution* s = new Solution();
69 
70     ListNode* l1 = new ListNode(9);
71     ListNode* l2 = new ListNode(9);
72 
73     ListNode* ans = s->addTwoNumbers(l1, l2);
74     while(ans){
75         cout << ans->val;
76         ans = ans->next;
77     }
78 
79     return 0;
80 }