LeetCode 445. Add Two Numbers II

最新推荐文章于 2025-06-01 17:29:22 发布

原创最新推荐文章于 2025-06-01 17:29:22 发布 · 308 阅读

0 ·

CC 4.0 BY-SA版权

文章标签：

#LeetCode #Add Two Numbers II

LeetCode练习题专栏收录该内容

168 篇文章

订阅专栏

本文介绍了LeetCode 445题“加两数 II”的两种解决方案，第一种使用栈避免链表翻转，第二种通过栈简化流程并优化代码。这两种方法都有效解决了题目要求的问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

LeetCode 445. Add Two Numbers II

Solution1：我的答案
利用了栈，这样就不用翻转链表了。。。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { //借助两个栈来运算
        if (l1 == NULL) 
            return l2;
        else if (l2 == NULL)
            return l1;
        int carry = 0;
        stack<struct ListNode*> List1, List2, res_stack;
        struct ListNode* temp1 = l1, * temp2 = l2, * res = new ListNode(-1);
        struct ListNode* temp_res = res;
        while (temp1 || temp2) {
            if (temp1) {
                List1.push(temp1);
                temp1 = temp1->next;
            }
            if (temp2) {
                List2.push(temp2);
                temp2 = temp2->next;
            }
        }
        int n1 = 0, n2 = 0;
        while (!List1.empty() || !List2.empty()) {
            if (!List1.empty()) {
                n1 = List1.top()->val;
                List1.pop();
            }
            else if(List1.empty())
                n1 = 0;
            if (!List2.empty()) {
                n2 = List2.top()->val;
                List2.pop();
            }
            else if(List2.empty())
                n2 = 0;
            int sum = n1 + n2 + carry;
            carry = sum/10;
            res_stack.push(new ListNode(sum%10));
        }
        if (carry) 
            res_stack.push(new ListNode(carry));
        while (!res_stack.empty()) {
            temp_res->next = res_stack.top();
            res_stack.pop();//原来stack的pop()操作并没有释放内存，虚惊一场~~~
            temp_res = temp_res->next;
        }
        return res->next;
    }
};

Solution2：
前半段思路相同，后半段思路要比我的好很多。。。实现的代码也大大优化了。。
参考网址：http://www.cnblogs.com/grandyang/p/6216480.html
思路：
我们首先遍历两个链表，将所有数字分别压入两个栈s1和s2中，我们建立一个值为0的res节点，然后开始循环，如果栈不为空，则将栈顶数字加入sum中，然后将res节点值赋为sum%10，然后新建一个进位节点head，赋值为sum/10，如果没有进位，那么就是0，然后我们head后面连上res，将res指向head，这样循环退出后，我们只要看res的值是否为0，为0返回res->next，不为0则返回res即可，参见代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
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 sum = 0;
        ListNode *res = new ListNode(0);
        while (!s1.empty() || !s2.empty()) {
            if (!s1.empty()) {sum += s1.top(); s1.pop();}
            if (!s2.empty()) {sum += s2.top(); s2.pop();}
            res->val = sum % 10;//为当前结点赋值
            ListNode *head = new ListNode(sum / 10);//以进位值初始化新建的前一个结点，这便于while执行完
            head->next = res;//后进行判断。新建的结点串在当前结点的前面。
            res = head; //结点更新，把新建的结点更新为下次循环时的当前结点
            sum /= 10;  //sum保留了此次循环的进位信息，喵喵喵！
        }
        return res->val == 0 ? res->next : res;
    }
};