题解 | #两个链表生成相加链表#

最开始的想法十分简单，读取两个链表，将链表保存的数据转为用int存储，然后相加，再存入结果链表中。代码如下。题目中给出的两个测试用例轻松通过。在我自信满满的点下提交后，第一个用例就没通过。事实证明我还是想的太简单了。

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

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        ListNode *p;
        int size1 = 0;
        int size2 = 0;
        long num1 = 0;
        long num2 = 0;
        p = head1;
        while(p != nullptr){
            size1++;
            p = p->next;
        }
        p = head2;
        while(p != nullptr){
            size2++;
            p = p->next;
        }
        p = head1;
        while(p != nullptr){
            num1 += p->val*pow(10,size1-1);
            size1--;
            p = p->next;
        }
        p = head2;
        while(p != nullptr){
            num2 += p->val*pow(10,size2-1);
            size2--;
            p = p->next;
        }
        long num = num1+num2;
        string s = to_string(num);
        ListNode *result;
        for(int i = 0;i < s.length();i++){
            if(i == 0){
                result = new ListNode(s[i]-'0');
                p = result;
                continue;
            }
            p->next = new ListNode(s[i]-'0');
            p = p->next;
        }
        return result;
    }
};

这种用链表存数肯定是有他的道理的，比如这个数大到任何基本数据类型都存不下。没错，第一个用例的数就大到离谱，我把int改为long都存不下。我意识到这题考的应该是大数加法。
在常规大数运算的题目中，操作数一般是以字符串给出，所以一般使用普通数组来存储操作数即可。但在本题中操作数是以链表形式给出，只能头指针开始读，而计算时需从尾部开始计算，所以选用先进后出的栈来保存数据。这样也不用考虑数组的对其问题，每次从两个栈的栈顶获取操作数，然后相加即可。进位的处理需要小心。代码中只有一重循环，时间复杂度为O(n)，使用了两个栈来辅助计算，空间复杂度为O(n)，代码如下。

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

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        stack<int> s1;
        stack<int> s2;
        int pre = 0;
        ListNode *result = nullptr;
        ListNode *p = nullptr;
        while(head1 != nullptr){
            s1.push(head1->val);
            head1 = head1->next;
        }
        while(head2 != nullptr){
            s2.push(head2->val);
            head2 = head2->next;
        }
        while(s1.size() > 0 && s2.size() > 0){
            int n = s1.top() + s2.top() + pre;
            s1.pop();
            s2.pop();
            pre = 0;
            if(n-10>=0){
                pre = 1;
                n -= 10;
            }
            result = new ListNode(n);
            result->next = p;
            p = result;
        }
        while(s1.size() > 0){
            int n = s1.top() + pre;
            s1.pop();
            pre = 0;
            if(n - 10 >= 0){
                pre = 1;
                n -= 10;
            }
            result = new ListNode(n);
            result->next = p;
            p = result;
        }
        while(s2.size() > 0){
            int n = s2.top() + pre;
            s2.pop();
            pre = 0;
            if(n - 10 >= 0){
                pre = 1;
                n -= 10;
            }
            result = new ListNode(n);
            result->next = p;
            p = result;
        }
        if(pre == 1){
            result = new ListNode(1);
            result->next = p;
        }
        return result;
    }
};