题解 | 链表相加(二) (栈存储链表元素)
链表相加(二)
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; } };#链表##栈#