445题

方法：翻转就要想到stack

/**
 * 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) {
        stack<int> sl1;
        stack<int> sl2;
        stack<int> sl3;
        ListNode* head=nullptr;
        ListNode* temp=nullptr;
        int carry=0;
        while(l1){
            sl1.emplace(l1->val);
            l1=l1->next;
        }
        while(l2){
            sl2.emplace(l2->val);
            l2=l2->next;
        }
        while(!sl1.empty()||!sl2.empty()){
            int n1=!sl1.empty()?sl1.top():0;
            if(!sl1.empty()){
                sl1.pop();
            }
            int n2=!sl2.empty()?sl2.top():0;
            if(!sl2.empty()){
                sl2.pop();
            }
            int sum=n1+n2+carry;
            sl3.emplace(sum%10);
            carry=sum/10;
        }
        if(carry){
            sl3.emplace(carry);
        }
        while(!sl3.empty()){
            int a=sl3.top();
            sl3.pop();
            if(!head){
                head=temp= new ListNode(a);
            }else{
                temp->next=new ListNode(a);
                temp=temp->next;
            }
        }
        return head;
    }
};

上述方法使用了三个栈，可以利用一个临时ListNode指针对数据进行反转

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1, s2;
        while (l1) {
            s1.push(l1 -> val);
            l1 = l1 -> next;
        }
        while (l2) {
            s2.push(l2 -> val);
            l2 = l2 -> next;
        }
        int carry = 0;
        ListNode* ans = nullptr;
        while (!s1.empty() or !s2.empty() or carry != 0) {
            int a = s1.empty() ? 0 : s1.top();
            int b = s2.empty() ? 0 : s2.top();
            if (!s1.empty()) s1.pop();
            if (!s2.empty()) s2.pop();
            int cur = a + b + carry;
            carry = cur / 10;
            cur %= 10;
            auto curnode = new ListNode(cur);
            curnode -> next = ans;
            ans = curnode;
        }
        return ans;
    }
};