[链表]BM11 链表相加(二)-中等
知识点链表模拟
描述
假设链表中每一个节点的值都在 0 - 9 之间,那么链表整体就可以代表一个整数。给定两个这种链表,请生成代表两个整数相加值的结果链表。数据范围:,链表任意值
要求:空间复杂度 ,时间复杂度
例如:链表 1 为 9->3->7,链表 2 为 6->3,最后生成新的结果链表为 1->0->0->0。
示例1
输入:
[9,3,7],[6,3]
复制返回值:
{1,0,0,0}
复制说明:
如题面解释
示例2
输入:
[0],[6,3]
复制返回值:
{6,3}
备注:
1 \leq n, m \leq 10^61≤n,m≤106
0 \leq a_i, b_i \leq 90≤ai,bi≤9
题解
#include <bits/stdc++.h>
struct ListNode
{
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(nullptr)
{
}
ListNode() = default;
};
ListNode *addInList(ListNode *head1, ListNode *head2)
{
if (head1 == nullptr)
{
return head2;
}
if (head2 == nullptr)
{
return head1;
}
std::stack<ListNode *> s1;
std::stack<ListNode *> s2;
int carray = 0;
while (head1 != nullptr)
{
s1.push(head1);
head1 = head1->next;
}
while (head2 != nullptr)
{
s2.push(head2);
head2 = head2->next;
}
std::stack<ListNode *> ans;
auto add_stack = [&ans](std::stack<ListNode *> &s, int &carray)
{
auto node = new ListNode(s.top()->val + carray);
carray = node->val / 10;
node->val = node->val % 10;
ans.push(node);
s.pop();
};
while (!s1.empty() || !s2.empty())
{
if (s1.empty())
{
add_stack(s2, carray);
continue;
}
if (s2.empty())
{
add_stack(s1, carray);
continue;
}
auto node = new ListNode(s1.top()->val + s2.top()->val + carray);
carray = node->val / 10;
node->val = node->val % 10;
ans.push(node);
s1.pop();
s2.pop();
}
if (carray > 0)
{
ans.push(new ListNode(1));
}
ListNode *list = nullptr;
ListNode *tail_node = nullptr;
while (!ans.empty())
{
if (list == nullptr)
{
list = ans.top();
tail_node = list;
}
else
{
tail_node->next = ans.top();
tail_node = tail_node->next;
}
ans.pop();
}
return list;
}