链表中的两数相加

​ 链表中的两数相加问题

2.两数相加 I

/**
 * 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) {
        ListNode* dummy = new ListNode(-1);
        ListNode* p=dummy;
        //进位值
        int carry=0; 
        while(l1 || l2){
            //短的那个链表后面用0代替其值
            int l1_val = l1 ? l1->val : 0; 
            int l2_val = l2 ? l2->val : 0;
            
            //相加
            int sum = l1_val + l2_val + carry; 
            //更新
            carry = sum/10; 
            sum = sum%10; 

            p->next = new ListNode(sum);
            p = p->next;
            
            if(l1!=nullptr) l1=l1->next;
            if(l2!=nullptr) l2=l2->next;
        }
        //两个链表全部遍历完毕，进位值不为0，在链表后面添加一个新结点
        if(carry>0){
            p->next = new ListNode(carry);
        }
        return dummy->next;
    }
};

445.两数相加 II

第一种方法：借助栈

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        //借助栈，逆序处理所有数位
        stack<int> st1, st2;
        while(l1){
            st1.push(l1->val);
            l1=l1->next;
        }
        while(l2){
            st2.push(l2->val);
            l2=l2->next;
        }

        ListNode* p=nullptr;
        int carry=0; //进位值
        while(!st1.empty() || !st2.empty()){
            int l1_val = st1.empty() ? 0 : st1.top();
            int l2_val = st2.empty() ? 0 : st2.top();
            if(!st1.empty()) st1.pop();
            if(!st2.empty()) st2.pop();

            int sum=l1_val+l2_val+carry;

            carry = sum/10;
            sum = sum%10;

            //反向建立单链表
            ListNode* cur = new ListNode(sum);
            cur->next = p;
            p = cur;

        }
        //两个链表全部遍历完毕，进位值不为0，再添加一个新结点
        if(carry>0){
            ListNode* cur = new ListNode(carry);
            cur->next = p;
            p = cur;
        }
        return p;
    }
};

第二种方法：借助反转链表

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = reve(l1);
        l2 = reve(l2);
        ListNode* dummy=new ListNode(-1);
        ListNode* p=dummy;
        int carry=0;
        while(l1 || l2){
            int val1 = l1 ? l1->val : 0;
            int val2 = l2 ? l2->val : 0;
            
            int sum = val1+val2+carry;
            carry = sum/10;
            sum = sum%10;
            
            p->next = new ListNode(sum);
            p=p->next;
            
            if(l1){
                l1=l1->next;
            }
            if(l2){
                l2=l2->next;
            }
        }
        if(carry>0){
            p->next = new ListNode(carry);
        }
        return reve(dummy->next);
    }
    
    //反转单链表
    ListNode* reve(ListNode* head){
        if(head==nullptr) return nullptr;
        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur){
            ListNode* nxt = cur->next;
    
            cur->next = pre;
            pre = cur;
            cur = nxt;
            
        }
        return pre;
    }
};

415.字符串相加

class Solution {
public:
    string addStrings(string num1, string num2) {
        int i=num1.size()-1;
        int j=num2.size()-1;
        int carry=0;
        string res="";
        while(i>=0 || j>=0 || carry!=0){
            int val1= i>=0 ? num1[i]-'0' : 0;
            int val2= j>=0 ? num2[j]-'0' : 0;

            int sum = val1+val2+carry;

            carry = sum/10;
            sum = sum%10;

            res.push_back(sum + '0');
            
            i--;
            j--;
        }
        reverse(res.begin(), res.end());

        return res;
    }
};