1 /* 2  * Easy 3  * 4  * @author: HZT 5  * @date: 2013-3-7 6  */ 7  8 #include 
     
       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 below21         // DO NOT write int main() function22         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 }