2.两数相加

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

解法1: 比较繁琐的写法

 1 class Solution {
 2 public:
 3     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
 4         int carry = 0;
 5         int v = l1->val + l2->val + carry;
 6         if(v >= 10)
 7         {
 8             carry = 1;
 9             v = v - 10;
10         }
11         ListNode* p = new ListNode(v);
12         ListNode* h = p;
13 
14         while(l1->next && l2->next){
15             int v = l1->next->val + l2->next->val + carry;
16             carry = 0;
17             if(v >= 10)
18             {
19                 carry = 1;
20                 v = v - 10;
21             }
22 
23             ListNode* q = new ListNode(v);
24             p->next = q;
25             p = p->next;
26 
27             l1 = l1->next;
28             l2 = l2->next;
29         }
30 
31         if(!l1->next)
32         {
33             while(l2->next)
34             {
35                 int v = l2->next->val + carry;
36                 carry = 0;
37                 if(v >= 10)
38                 {
39                     carry = 1;
40                     v = v - 10;
41                 }
42 
43                 ListNode* q = new ListNode(v);
44                 p->next = q;
45                 p = p->next;
46                 l2 = l2->next;
47             }
48         }
49 
50         if(!l2->next)
51         {
52             while(l1->next)
53             {
54                 int v = l1->next->val + carry;
55                 carry = 0;
56                 if(v >= 10)
57                 {
58                     carry = 1;
59                     v = v - 10;
60                 }
61 
62                 ListNode* q = new ListNode(v);
63                 p->next = q;
64                 p = p->next;
65                 l1 = l1->next;
66             }
67         }
68 
69         if(!l1->next && !l2->next && carry == 1)
70         {
71             ListNode* q = new ListNode(1);
72             p->next = q;
73         }
74 
75         return h;
76     }
77 };

解法2: 一次循环

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

        ListNode *pRet = 0, *pFirst = 0;
        int nAdd = 0, nSum = 0;

       while(l1 || l2)
       {
            nSum = nAdd;
            if (l1)
            {
                nSum += l1->val;
                l1 = l1->next;
            }
            if (l2)
            {
                nSum += l2->val;
                l2 = l2->next;
            }
            nAdd = nSum > 9;
            auto pNew = new ListNode(nSum%10);
            if (pFirst)
                pFirst = pFirst->next = pNew;
            else
                pFirst = pRet = pNew;
        }

        if (nAdd)
             pFirst = pFirst->next = new ListNode(1);

        return pRet;
    }