445. 两数相加 II

题目

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例1：

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

难度：中等

题解

通过观察可以发现，做加法的顺序是相反的，为了逆序处理所有数位，可以使用栈：把所有的数字压入栈中，再依次取出相加。计算过程中需要注意进位的情况

/**
 * 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> s1,s2;   //两个栈用于反转链表
    while(l1) {
        s1.push(l1->val);
        l1=l1->next;
    }
    while(l2){
        s2.push(l2->val);
        l2=l2->next;
    }
    int n1=s1.size()-1,n2=s2.size()-1;
    int sum=0,top1,top2;
    ListNode *first,*p=NULL;
    while(n1>=0 || n2>=0 || sum>0){
        top1=top2=0;
        if(n1>=0){
            top1=s1.top();
            s1.pop();
            n1--;
        }
        if(n2>=0){
            top2=s2.top();
            s2.pop();
            n2--;
        }
        sum+=top1+top2;
        ListNode *t=new ListNode(sum%10);
        first=t;
        t->next=p;
        p=t;
        sum/=10;
    }
    return first;
    }
};

复杂度分析

• 时间复杂度：O（max（n1，n2），其中n1，n2位两个链表的长度
• 空间复杂度：O(n1+n2)，空间复杂度主要取决于吧链表内容放进栈中所用的空间