445. 兩數(shù)相加 II

題目描述

給你兩個(gè) 非空 鏈表來代表兩個(gè)非負(fù)整數(shù)。數(shù)字最高位位于鏈表開始位置。它們的每個(gè)節(jié)點(diǎn)只存儲(chǔ)一位數(shù)字。將這兩數(shù)相加會(huì)返回一個(gè)新的鏈表。

你可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)字都不會(huì)以零開頭。

示例1：

輸入：l1 = [7,2,4,3], l2 = [5,6,4]
輸出：[7,8,0,7]

示例2：

輸入：l1 = [2,4,3], l2 = [5,6,4]
輸出：[8,0,7]

示例3：

輸入：l1 = [0], l2 = [0]
輸出：[0]

提示：

鏈表的長度范圍為 [1, 100]
0 <= node.val <= 9
輸入數(shù)據(jù)保證鏈表代表的數(shù)字無前導(dǎo) 0

進(jìn)階：如果輸入鏈表不能翻轉(zhuǎn)該如何解決？

解題思路

思路：棧+豎式加法。分別使用棧st1、st2存儲(chǔ)鏈表1、2元素，使用sum表示當(dāng)前和，使用add表示進(jìn)位，使用cur表示當(dāng)前位。首先是兩個(gè)指針均不為空時(shí)的處理，接著是兩個(gè)指針兩者之一為空時(shí)的處理，最后要注意殘留add時(shí)的處理。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        //既然鏈表正序存儲(chǔ) 那么就使用棧來存儲(chǔ) 利用棧先進(jìn)后出的性質(zhì)
        stack<int> st1,st2;
        while(l1)
        {
            st1.push(l1->val);
            l1=l1->next;
        }
        while(l2)
        {
            st2.push(l2->val);
            l2=l2->next;
        }
        //剩下的本質(zhì)上和2一樣
        int sum;
        int cur;
        int add=0;
        ListNode* L=new ListNode();
        while(!st1.empty()&&!st2.empty())
        {
            sum=(st1.top()+st2.top()+add);
            cur=sum%10;
            add=sum/10;
            ListNode* temp=new ListNode(cur);
            temp->next=L->next;
            L->next=temp;
            st1.pop();
            st2.pop();
        }
        while(!st1.empty())
        {
            sum=(st1.top()+add);
            cur=sum%10;
            add=sum/10;
            ListNode* temp=new ListNode(cur);
            temp->next=L->next;
            L->next=temp;
            st1.pop();
        }
        while(!st2.empty())
        {
            sum=(st2.top()+add);
            cur=sum%10;
            add=sum/10;
            ListNode* temp=new ListNode(cur);
            temp->next=L->next;
            L->next=temp;
            st2.pop();
        }
        if(add)
        {
            ListNode* temp=new ListNode(add);
            temp->next=L->next;
            L->next=temp;
        }
        return L->next;
    }
};

總結(jié)：兩數(shù)相加II和兩數(shù)相加的唯一區(qū)別在于，兩數(shù)相加中的數(shù)是逆序存儲(chǔ)，而兩數(shù)相加II中的數(shù)是正序存儲(chǔ)。兩數(shù)相加的直觀思維是豎式加法，而豎式加法正好滿足逆序，現(xiàn)在既然是正序，那么就可以考慮如何將正序轉(zhuǎn)換為逆序，此時(shí)正好利用棧結(jié)構(gòu)的特性即可。

代碼可能稍顯冗余，但是思路較為清晰。文章來源地址http://www.zghlxwxcb.cn/news/detail-516548.html

到了這里，關(guān)于【每日一題】445. 兩數(shù)相加 II的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！