BM11. 链表相加(二)
描述
示例1
输入:
[9,3,7],[6,3]
输出:
{1,0,0,0}
说明:
如题面解释示例2
输入:
[0],[6,3]
输出:
{6,3}
C++ 解法, 执行用时: 55ms, 内存消耗: 21840KB, 提交时间: 2021-09-07
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
static const auto io_sync_off =[] ()
{
std::ios::sync_with_stdio(false);
std:;cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
ListNode* addInList(ListNode* head1, ListNode* head2) {
// write code here
if(head1 == nullptr) return head2;
if(head2 == nullptr) return head1;
stack<int> s1;
stack<int> s2;
stack<int> stk;
ListNode* cur = head1;
while(head1->next){
s1.push(head1->val);
head1 = head1->next;
}
s1.push(head1->val);
head1->next = head2;
while(head2){
s2.push(head2->val);
head2 = head2->next;
}
int temp = 0;
int jw = 0;
while(!s1.empty() && !s2.empty()){
temp = s1.top()+s2.top()+jw;
s1.pop();
s2.pop();
if(temp>=10){
jw=temp/10;
temp-=10;
}else
jw=0;
stk.push(temp);
}
while(s1.empty() && !s2.empty()){
temp=s2.top()+jw;
s2.pop();
if(temp>=10){
jw=temp/10;
temp-=10;
}
else jw=0;
stk.push(temp);
}
while(!s1.empty() && s2.empty()){
temp = s1.top()+jw;
s1.pop();
if(temp>=10){
jw=temp/10;
temp-=10;
}else
jw=0;
stk.push(temp);
}
if(jw!=0){
stk.push(jw);
}
head1=cur;
while(!stk.empty()){
cur->val=stk.top();
stk.pop();
if(stk.empty())
break;
cur = cur->next;
}
cur->next=nullptr;
return head1;
}
};
C++ 解法, 执行用时: 57ms, 内存消耗: 21892KB, 提交时间: 2021-06-26
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
ListNode* addInList(ListNode* head1, ListNode* head2) {
// write code here
if (head1 == nullptr) return head2;
if (head2 == nullptr) return head1;
stack<int> s1;
stack<int> s2;
stack<int> stk;
ListNode* cur = head1;
while (head1->next)
{
s1.push(head1->val);
head1 = head1->next;
}
s1.push(head1->val);
head1->next = head2;
while (head2)
{
s2.push(head2->val);
head2 = head2->next;
}
int temp = 0;
int jw = 0;
while (!s1.empty() && !s2.empty())
{
temp = s1.top() + s2.top() + jw;
s1.pop();
s2.pop();
if (temp >= 10)
{
jw = temp / 10;
temp -= 10;
}
else jw = 0;
stk.push(temp);
}
while (s1.empty() && !s2.empty())
{
temp = s2.top() + jw;
s2.pop();
if (temp >= 10)
{
jw = temp / 10;
temp -= 10;
}
else jw = 0;
stk.push(temp);
}
while (!s1.empty() && s2.empty())
{
temp = s1.top() + jw;
s1.pop();
if (temp >= 10)
{
jw = temp / 10;
temp -= 10;
}
else jw = 0;
stk.push(temp);
}
if (jw != 0)
stk.push(jw);
head1 = cur;
while (!stk.empty())
{
cur->val = stk.top();
stk.pop();
if (stk.empty())
break;
cur = cur->next;
}
head2 = cur->next;;
cur->next = nullptr;
return head1;
}
};
static const auto io_sync_off =[] ()
{
std::ios::sync_with_stdio(false);
std:;cin.tie(nullptr);
return nullptr;
}();
C++ 解法, 执行用时: 57ms, 内存消耗: 21976KB, 提交时间: 2021-06-27
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
ListNode* addInList(ListNode* head1, ListNode* head2) {
// write code here
if (head1 == nullptr) return head2;
if (head2 == nullptr) return head1;
stack<int> s1;
stack<int> s2;
stack<int> stk;
ListNode* cur = head1;
while (head1->next)
{
s1.push(head1->val);
head1 = head1->next;
}
s1.push(head1->val);
head1->next = head2;
while (head2)
{
s2.push(head2->val);
head2 = head2->next;
}
int temp = 0;
int jw = 0;
while (!s1.empty() && !s2.empty())
{
temp = s1.top() + s2.top() + jw;
s1.pop();
s2.pop();
if (temp >= 10)
{
jw = temp / 10;
temp -= 10;
}
else jw = 0;
stk.push(temp);
}
while (s1.empty() && !s2.empty())
{
temp = s2.top() + jw;
s2.pop();
if (temp >= 10)
{
jw = temp / 10;
temp -= 10;
}
else jw = 0;
stk.push(temp);
}
while (!s1.empty() && s2.empty())
{
temp = s1.top() + jw;
s1.pop();
if (temp >= 10)
{
jw = temp / 10;
temp -= 10;
}
else jw = 0;
stk.push(temp);
}
if (jw != 0)
stk.push(jw);
head1 = cur;
while (!stk.empty())
{
cur->val = stk.top();
stk.pop();
if (stk.empty())
break;
cur = cur->next;
}
head2 = cur->next;;
cur->next = nullptr;
return head1;
}
};
static const auto io_sync_off =[] ()
{
std::ios::sync_with_stdio(false);
std:;cin.tie(nullptr);
return nullptr;
}();
C++ 解法, 执行用时: 58ms, 内存消耗: 21376KB, 提交时间: 2021-05-19
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
static const auto io_sync_off=[]()
{
//turn off sync
std::ios::sync_with_stdio(false);
//untie in/out stream;
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
ListNode* addInList(ListNode* head1, ListNode* head2) {
int a=0,b=0; //记录链表的长度,reverse运行完，a,b返回链表的长度
head1=reverse(head1,a);
head2=reverse(head2,b);
if(a<b) swap(head1,head2); //长的作为链表1
ListNode *record=head1;
bool carry=0;
while(head2) //链表2短，因此只需先遍历链表2
{
int temp=head1->val+head2->val+carry;
carry=0;
if(temp>=10)
{
carry=1;
temp%=10;
}
head1->val=temp; //直接在链表1上面进行修改
head2=head2->next;
if(head2)
{
head1=head1->next;
}
}
while(carry){
//在链表1上处理进位
carry=0;
if(head1->next){ //判断有没有下一位
head1=head1->next;
if(head1->val == 9) {
//直接判断是不是9
carry = 1;
//是9则进位
head1->val = 0;
//并且设置为0
}
else head1->val++;
}
else head1->next=new ListNode(0);
}
return reverse(record,a);
// write code here
}
ListNode* reverse(ListNode* ln,int &length){
ListNode* pre=nullptr;
ListNode* cur=ln;
ListNode* next=nullptr;
while(cur)
{
next=cur->next; //在指针断开之前，保存下后续结点
cur->next=pre; //改变指向，指向前一个结点
pre=cur;
cur=next;
length++;
}
return pre;
}
};
C++ 解法, 执行用时: 59ms, 内存消耗: 20396KB, 提交时间: 2021-04-22
static const auto io_sync_off=[]()
{
//turn off sync
std::ios::sync_with_stdio(false);
//untie in/out stream;
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
ListNode* addInList(ListNode* head1, ListNode* head2) {
int a = 0, b = 0; //记录链表长度
head1 = reverse(head1, a); //翻转链表1并返回头
head2 = reverse(head2, b); //翻转链表2并返回头
if(a < b) swap(head1, head2); //让较长的链表作为链表1
ListNode* record = head1; //记录链表1的头，用于后续再次翻转
bool carry = 0; //记录进位信息
while(head2) { //因为链表2短，因此只需先遍历链表2
int temp = head1->val + head2->val + carry; //各位及进位相加
carry = 0; //进位符清零
if(temp >= 10) { //若进位
carry = 1; //设置进位符
temp %= 10; //取余
}
head1->val = temp; //直接在链表1上修改值
head2 = head2->next; //链表2向前
if(head2) //判断一下链表2是否遍历完
head1 = head1->next; //如果没遍历完，则链表1肯定也没遍历完，这样不至于让head1成为nullptr方便后续操作
}
while(carry) { //接着在链表1上处理进位
carry = 0; //进位符清零
if(head1->next) { //先判断有没有下一位
head1 = head1->next; //有的话移到下一位
if(head1->val == 9) { //直接判断是不是9
carry = 1; //是9则进位
head1->val = 0; //并且设置为0
}
else head1->val ++; //否则自身加1
}
else head1->next = new ListNode(1); //若无下一位创造值为1的新ListNode
}
return reverse(record, a); //返回翻转链表1的头
}
ListNode* reverse(ListNode* ln, int &length) { //翻转链表懂的都懂，引用length记录长度
ListNode* pre = nullptr;
ListNode* cur = ln;
ListNode* next = nullptr;
while(cur) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
length++;
}
return pre;
}
};