/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ ListNode* addInList(ListNode* head1, ListNode* head2) { // 栈1栈2 用于逆置head1中的值 stack<ListNode*> list1; stack<ListNode*> list2; // 用存放要输出的值 stack<int> out; // 将head1 head2 中的节点依此放入栈中 auto* it = head1; while (it != nullptr) { list1.push(it); it = it->next; } it = head2; while (it != nullptr) { list2.push(it); it = it->next; } // 数据处理 // 将栈1 栈2中的值依此取出进行相加 // next 用于处理进位 // thiss存放本次要入栈的值 int next = 0; int thiss = 0; while(!list1.empty() && !list2.empty()) { thiss = list1.top()->val + list2.top()->val + next; list1.pop(); list2.pop(); next = 0; // 若需要进位则next赋值为1 if (thiss >= 10) { next = 1; thiss = thiss % 10; } out.push(thiss); } // 若list1 长度大于 list2 // 处理方法同上 while (!list1.empty()) { int thiss = list1.top()->val + next; list1.pop(); next = 0; if (thiss >= 10) { next = 1; thiss = thiss % 10; } out.push(thiss); } // 若list1 长度小于 list2 // 处理方法同上 while (!list2.empty()) { int thiss = list2.top()->val + next; list2.pop(); next = 0; if (thiss >= 10) { next = 1; thiss = thiss % 10; } out.push(thiss); } // 处理最末尾数字 if (next == 1) { out.push(1); } // 数据处理结束 // 此时out栈中的数据即为最终输出数据的逆置 // 重新创建链表存放最终数据 auto* newHead = new ListNode(0); auto* i = newHead; while (!out.empty()) { i->next = new ListNode(out.top()); out.pop(); i = i->next; } return newHead->next; } };