LeetCode --- 2. Add Two Numbers

LeetCode --- 2. Add Two Numbers

題目鏈接：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

這道題的要求是將用鏈表表示的兩個數（數字以相反順序存儲）相加，並返回加和之後的鏈表。

思路是首先將第二個鏈表的每個節點加到第一個鏈表對應的節點上（當然新建鏈表節點也可以），然後如果第二個鏈表有剩余，就將其全部加到第一個鏈表後面。最後再依次處理進位。值得注意的是最後的進位哦。。。

時間復雜度：O(n)

空間復雜度：O(1)

 1 class Solution
 2 {
 3 public:
 4     ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
 5     {
 6         if(l1 == NULL)
 7             return l2;
 8         if(l2 == NULL)
 9             return l1;
10         
11         ListNode *p1 = l1, *p2 = l2;
12         while(p1 -> next != NULL && p2 -> next != NULL)
13         {
14             p1 -> val += p2 -> val;
15             
16             p1 = p1 -> next;
17             p2 = p2 -> next;
18         }
19         p1 -> val += p2 -> val;
20         
21         if(p1 -> next == NULL)
22             p1 -> next = p2 -> next;
23         
24         int a, c = 0;
25         ListNode *p = l1;
26         while(p -> next != NULL)
27         {
28             a = p -> val + c;
29             p -> val = a % 10;
30             c = a / 10;
31             
32             p = p -> next;
33         }
34         a = p -> val + c;
35         p -> val = a % 10;
36         c = a / 10;
37         
38         if(c == 1)
39         {
40             ListNode *pln = new ListNode(1);
41             p -> next = pln;
42         }
43         
44         return l1;
45     }
46 };

上面代碼太長了。。。下面在兩個鏈表對應節點相加的時候，同時用變量c維護進位，這樣1次循環就都搞定了。

 1 class Solution
 2 {
 3 public:
 4     ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
 5     {
 6         ListNode *h = new ListNode(0), *cur = h;
 7         int c = 0;
 8         while(l1 != NULL || l2 != NULL)
 9         {
10             int a1 = l1 != NULL ? l1 -> val : 0;
11             int a2 = l2 != NULL ? l2 -> val : 0;
12             int a = a1 + a2 + c;
13             c = a / 10;
14             cur -> next = new ListNode(a % 10);
15             cur = cur -> next;
16             if(l1 != NULL)
17                 l1 = l1 -> next;
18             if(l2 != NULL)
19                 l2 = l2 -> next;
20         }
21         if(c > 0)
22             cur -> next = new ListNode(c);
23         return h -> next;
24     }
25 };