题意分析

  • 给出两个链表，这两个链表代表两个数字（注意，这个数字可能很大,大数),从表头到表尾表示的是这个链表的高位到低位。需要我们将这两个链表的数字进行相加，然后构造一个新的链表表示出这个和。

  • 样例解释请看下面的图

图片说明

思路分析

  • 首先，我们可以看到这个题目的本质就是一个大数加法运算，两个链表存储的数字的长度很长，需要先将这两个链表代表的数字相加，然后构造出一个新的链表存储这个和。首先，我们看大数加法运算，这个可以用字符串表示这两个数字，然后模拟大数加法的操作。最后构造出一个新的链表即可。
  • 这里大数高精度运算是核心，但是思路比较简单，就是按照我们小学的时候进行加法运算的操作进行处理就行了。从低位开始进行运算，记录下进位和当前位置的数字，最后就可以得到大数相加的和了。另外一点要注意的就是如果两个数字的位数不一样，最好还是先通过前面补0使两个数字的位数相同。这样便于我们进行操作。

解法一 字符串版

  • 这种写法是利用字符串存储两个数字进行处理，比较常规的做法。
  • 代码如下
    • 需要遍历两个链表，时间复杂度为O(lena+lenb)
    • 需要存储两个链表，空间复杂度为O(lena+lenb) 
/**
 * 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
        string a,b;
        // 先将两个链表里面的数据分别存入两个字符串
        while(head1){
            a+=(head1->val+'0');
            head1=head1->next;
        }
        while(head2){
            b+=(head2->val+'0');
            head2=head2->next;
        }
        int lena=a.size();
        int lenb=b.size();
        // 如果两个字符串的长度不相同，在短的那一个字符串的前面补0
        while(lena<lenb){
            lena++;
            a="0"+a;
        }
        while(lenb<lena){
            lenb++;
            b="0"+b;
        }
        int cnt=0;
        vector<int> ans;
        int x=lenb-1;
        // 模拟进行大数加法运算
        while(x>=0){
            int tmp=a[x]-'0'+b[x]-'0'+cnt;
            cnt=tmp/10;
            tmp%=10;
            ans.push_back(tmp);
            x--;
        }
        // 注意最后的进位
        if(cnt){
            ans.push_back(cnt);
        }
//         for(auto y:ans){
//             std::cout<<y<<endl;
//         }
        x=lenb-1;
        ListNode* now=new ListNode(ans[x--]);
        ListNode* head=now;
        // 构建一个新的链表
        while(x>=0){
            ListNode* now1 = new ListNode(ans[x--]);
            now->next=now1;
            now=now1;
        }
        return head;
    }
};

解法二 用栈模拟

  • 这个写法是利用栈的先进后出的性质，如下

图片说明

  • 我们遍历链表的时候，发现低位反倒是最后遍历的，如果使用栈的话，我们发现我们取的时候正好是低位，那么可以直接取栈顶进行操作。然后最后的结果我们发现高位也是最后得到的，而我们构造链表的时候恰好就是先用高位构造，这不也是我们想要的吗？所以这个题目用栈是最方便的，不要在进行顺序的变换。

  • 代码如下

    • 需要遍历两个链表，时间复杂度为O(lena+lenb)
    • 需要存储两个链表，空间复杂度为O(lena+lenb) 
/**
 * 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> a,b;  // 利用两个栈来存储这两个链表的值
        while(head1){
            a.push(head1->val);
            head1=head1->next;
        }
        while(head2){
            b.push(head2->val);
            head2=head2->next;
        }

        int cnt=0;
        stack<int> ans;
        // 不断遍历两个链表，模拟大数加法运算
        while(!a.empty()||!b.empty()){
            int tmp=0;
            // 注意如果栈为空的时候不能遍历再执行出栈操作
            if(!a.empty()){
                tmp+=a.top();
                a.pop();
            }
            if(!b.empty()){
                tmp+=b.top();
                b.pop();
            }
            tmp+=cnt;
            cnt=tmp/10;
            tmp%=10;
            ans.push(tmp);
        }
        // 最后存在进位操作
        if(cnt){
            ans.push(cnt);
        }
        ListNode* now=new ListNode(ans.top());
        ListNode* head=now;
        ans.pop();
        // 重建这个链表
        while(!ans.empty()){
            ListNode* now1=new ListNode(ans.top());
            ans.pop();
            now->next=now1;
            now=now1;
        }

        return head;
    }
};