题解 | #链表相加(二)#

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        stack<int> t1;
        stack<int> t2;
        ListNode* p = new ListNode(-1);
        ListNode* c = nullptr;
        p->next = c;
        ListNode* m = head1;
        ListNode* n = head2;

        while (m) {
            t1.push(m->val);
            m = m->next;
        }
        while (n) {
            t2.push(n->val);
            n = n->next;
        }
        int add = 0;
        while (!t1.empty() && !t2.empty()) {

            int nums = 0;
            int x = t1.top();
            int y = t2.top();
            t1.pop();
            t2.pop();
            if (x + y + add >= 10) {
                nums = x + y + add - 10;
                add = 1;
            } else {
                nums = x + y + add;
                add = 0;
            }
            ListNode* temp = new ListNode(nums);
            cout << nums;
            temp->next = c;
            c = temp;
        }
        while (!t1.empty()) {
            int x = t1.top();
            t1.pop();
            int numst1 = 0;
            if (x + add >= 10) {
                numst1 = x + add - 10;
                add = 1;
            } else {
                numst1 = x + add;
                add = 0;
            }
            ListNode* temp = new ListNode(numst1);
            cout<<"t1不为空时"<<numst1;
            temp->next = c;
            c = temp;

        }
        while (!t2.empty()) {
            int y = t2.top();
            t2.pop();
            int numst2 = 0;
            if (y + add >= 10) {
                numst2 = y + add - 10;
                add = 1;
            } else {
                numst2 = y + add;
                add = 0;
            }
            ListNode* temp = new ListNode(numst2);
            // cout<<nums;
            temp->next = c;
            c = temp;

        }
        if(add==1){
                     ListNode* temp = new ListNode(add);
            // cout<<nums;
            temp->next = c;
            c = temp; 
        }
        return c;
    }


};

思路：常规从低位相加，同时计算是否进位。我们首先用栈，先把链表按顺序入栈，这样先出栈的就是低位。

    while (m) {
        t1.push(m->val);
        m = m->next;
    }
    while (n) {
        t2.push(n->val);
        n = n->next;
    }

这部分就是存栈。

接下来需要进行处理，因为两个栈可能长度不同。需要区分，两个数相加，对应位置都有值时怎么做，当其中一个数值位已经没有值时怎么做。

    while (!t1.empty() && !t2.empty()) {

        int nums = 0;
        int x = t1.top();
        int y = t2.top();
        t1.pop();
        t2.pop();
        if (x + y + add >= 10) {
            nums = x + y + add - 10;
            add = 1;
        } else {
            nums = x + y + add;
            add = 0;
        }
        ListNode* temp = new ListNode(nums);
        cout << nums;
        temp->next = c;
        c = temp;
    }

当两个栈都非空时，保证两个栈都有元素top,按位加法，x+y,如果大于等于10，就要进位。高一位的x+y,如果低一位有进位就变成了x+y+1。 我们把进位标记出来，add，是否需要进位。初始状态不需要进位。add=0.x+y+add>=10时，链表中存的数就变成了x+y+add-10, 然后把add置为1。如果 x+y+add<10,那么直接存x+y+add。add置为0。这样就是给高一位提供了进位信号。

链表采用头插法。初始化一个空指针。temp->next=c,然后c=temp.

当两个栈中其中有一个栈用完的时候，剩下另一个栈中还有值。 例如

    while (!t1.empty()) {
        int x = t1.top();
        t1.pop();
        int numst1 = 0;
        if (x + add >= 10) {
            numst1 = x + add - 10;
            add = 1;
        } else {
            numst1 = x + add;
            add = 0;
        }
        ListNode* temp = new ListNode(numst1);
        cout<<"t1不为空时"<<numst1;
        temp->next = c;
        c = temp;

    }

仍然是继续出栈，当时此时没有两个出栈元素的加法，不过仍然需要考虑进位信号。换成若是t2非空也一样。这样一直到两个栈都空了，这样就结束了？

其实并不然，是否有可以两个三位数，加起来变成四位数？就是需要考虑最高位是否有进位。当两个栈出完了，最后的进位信号是什么，如果是0，就不会有多一位。如果是1，仍然需要再进位多出一位。

   if(add==1){
                 ListNode* temp = new ListNode(add);
        // cout<<nums;
        temp->next = c;
        c = temp; 
    }

最后返回c.