题解 | 链表相加(二) (栈存储链表元素)

链表相加(二)

https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <cstddef>
#include <stack>
using namespace std;

class Solution {
public:
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        stack<int> a, b;
        // 将链表节点值压入栈中
        while (head1 != nullptr) {
            a.push(head1->val);
            head1 = head1->next;
        }
        while (head2 != nullptr) {
            b.push(head2->val);
            head2 = head2->next;
        }

        ListNode* dummy = new ListNode(0); // 创建哑节点作为结果链表头
        int carry = 0; // 进位值

        while (!a.empty() || !b.empty() || carry != 0) {
            int x = 0, y = 0;
            // 安全获取栈顶元素(栈空时为0)
            if (!a.empty()) {
                x = a.top();
                a.pop();
            }
            if (!b.empty()) {
                y = b.top();
                b.pop();
            }
            
            int sum = x + y + carry;
            carry = sum / 10;      // 计算进位
            int digit = sum % 10;  // 计算当前位值
            
            // 头插法创建新节点
            ListNode* newNode = new ListNode(digit);
            newNode->next = dummy->next;
            dummy->next = newNode;
        }
        
        return dummy->next;
    }
};

#链表##栈#
全部评论

相关推荐

DBsan:我也遇到过好的HR,全程友好交流。这年头基本的礼貌和尊重为什么好多HR都做不到
找工作时遇到的神仙HR
点赞 评论 收藏
分享
如题,求问华为1145和25定律是什么意思?刷到好多人说这个东西了,不知道什么意思
我能加班:如果你在主管面试完当天晚上11点45分收到面试反馈邮件的话,大概率是通过主管面试了。25小时是指在你主管面完成收到短信后的25小时你可以在官网查到你是不是通过。 应该是这样
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务