日期：20180910

題目描述：

You are given two non-empty linked lists representing two non-negative integers. 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.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Examples：

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

詳解：

這題難度為medium，難點有三：

1. 這題的輸出是一個鏈表，如果我們構(gòu)建一個鏈表，最后一定得到的是鏈尾元素，但是函數(shù)返回的應(yīng)該是鏈頭元素，所以為了解決這個問題，將鏈頭元素賦予一個額外的指針指向它。

2. 另外，我們每次增添一個節(jié)點都要用到上一個節(jié)點的值，例如tmp->next = new ListNode(sum%10)，tmp就是上一個節(jié)點。但是第一個節(jié)點怎么辦，第一個節(jié)點沒有上一個節(jié)點。解決辦法就是犧牲頭節(jié)點，第一個節(jié)點隨便賦一個值，從然后讓tmp和result都指向它，之后開始循環(huán)。最后返回result->next。

3. 如果聲明一個指向鏈表節(jié)點的指針，之后直接用的話會報錯。

   ListNode* result；
   result->val = 0；//會報錯member access within null pointer of type ‘struct ListNode’ 
   

   因為這么做相當于聲明了一個指針，卻沒有賦初值，編譯器并不知道result指向哪里。這里如果想解決這個問題就要用到動態(tài)內(nèi)存了。

   ListNode* result = new ListNode(0);
   cout<<result->val;   //會正確的輸出0。
   

   用動態(tài)內(nèi)存new運算符，自動為新的節(jié)點分配一塊內(nèi)存，內(nèi)存地址也會返回到result，result也就成為了指向該地址的指針。

知道了這三個難點，程序設(shè)計起來便不會太費勁。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *result = new ListNode(0);
        ListNode *tmp = result;
        int sum = 0;
        while(l1 || l2){      
            if(l1){
                sum += l1->val;
                l1 = l1->next;
            }
            if(l2){
                sum += l2->val;
                l2 = l2->next;
            }
            tmp->next = new ListNode(sum%10);
            sum /= 10;
            tmp = tmp->next;
        }
        if(sum)
            tmp->next = new ListNode(1);
        return result->next;
    }
};

提交答案之后用時是50ms，看了一下28ms的答案，如下所示：

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *tail = new ListNode(0);
        ListNode *result = tail;
        bool carry = false;
        while(l1 != NULL || l2 != NULL) {
            int x = 0;
            int y = 0;
            if (l1 != NULL) {
                x = l1->val;
                l1 = l1->next;
            }
            if (l2 != NULL) {
                y = l2->val;
                l2 = l2->next;
            }
            int sum = x + y;
            if (carry) {
                sum += 1;
                carry = false;
            }
            if (sum >= 10) {
                carry = true;
                sum -= 10;
            }
            tail->val = sum;
            if (l1 != NULL || l2 != NULL) {
                tail->next = new ListNode(0);
                tail = tail->next;
            }
        }
        // Add the last carried digit, if there is one.
        if (carry) {
            tail->next = new ListNode(1);
            tail = tail->next;
        }
        return result;
    }
};

其實和我的基本是一樣的，只不過針對剛才說的難點2，他的解決方法不一樣。我是先判斷好這次能不能在之前的節(jié)點后新加節(jié)點，如果能就新加一個。而他的思路是，把當前節(jié)點的val改成sum值，然后如果接下來還有就新增加一個節(jié)點留著下次用，如果算完了就不加了，最后還是指向NULL。然后全部結(jié)束后還得判斷一下有沒有進位，如果有還得再添一個1。

我的辦法代碼簡潔，但是想的時候我頭很大，他的辦法容易想，不過判斷各種條件比較麻煩。在我的印象中老外寫代碼總是很簡單粗暴。不過他的代碼和我的計算速度還是在一個數(shù)量級，畢竟方法基本一樣的，他的快一點可能以為一些其他玄學因素吧。