当前位置:网站首页>Addition of linked lists (2)
Addition of linked lists (2)
2022-08-10 22:30:00 【dry rice white】
Get this question,One question I've been thinking about is,Can it be done without pre-traversing.
呜呜,原谅我的无知,我想不出来.
Then just traverse it once,It doesn't affect the time anyway.
一看到这题,There are two ways to solve the problem,The first is to save the data in the two linked lists in advance through two arrays,Then it becomes the addition of large numbers,Then put the result into a new linked list.
Another is to add a short linked list,The individual bits are then added,最后考虑进位.等等,好像不可以吧,如果这样的话,Carry can't be solved,It is a singly linked list after all.如果可行,Finally, it is necessary to use the array to complete the carry.
I will try both methods!!!
解法1:At first I thought about saving along the way,In this way, the data can be put into the array when the length is counted.In the end, the carry was found to be difficult to handle
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
int *arr1 = new int[1000002]; //用来保存结果
int *arr2 = new int[1000002];
ListNode* addInList(ListNode* head1, ListNode* head2) {
// write code here
//末尾对齐,遍历一遍
int len1 = 0;
int len2 = 0;
ListNode *p1 = head1;
ListNode *p2 = head2;
while(p1 != nullptr)
{
p1 = p1->next;
len1++;
}
while(p2 != nullptr)
{
p2 = p2->next;
len2++;
}
//Save the individual digits into an array
p1 = head1;
for(int i=len1-1;i>=0;--i)
{
arr1[i] = p1->val;
p1 = p1->next;
}
p2 = head2;
for(int i=len2-1;i>=0;--i)
{
arr2[i] = p2->val;
p2 = p2->next;
}
//Add the individual bits
int len = len1 > len2 ? len1:len2;
for(int i=0;i<len;++i)
{
arr1[i] = arr1[i] + arr2[i];
arr1[i+1] = arr1[i+1] + arr1[i]/10;
arr1[i] = arr1[i]%10;
}
ListNode *ans = nullptr;
ListNode *p = nullptr;
if(arr1[len] > 0)
{
ListNode *s = new ListNode(arr1[len]);
s->next = nullptr;
ans = s;
p = s;
}
for(int k=len-1;k>=0;k--)
{
ListNode *s = new ListNode(arr1[k]);
s->next = nullptr;
if(ans == nullptr)
{
ans = s;
p = s;
}
else
{
p->next = s;
p = p->next;
}
}
return ans;
}
};
It seems that I forgot to free the memory in the array here,一个好的习惯,Still recommend to release it
解法2:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
ListNode* addInList(ListNode* head1, ListNode* head2) {
// write code here
//末尾对齐,遍历一遍
int len1 = 0;
int len2 = 0;
ListNode *p1 = head1;
ListNode *p2 = head2;
while(p1 != nullptr)
{
p1 = p1->next;
len1++;
}
while(p2 != nullptr)
{
p2 = p2->next;
len2++;
}
if(len1 > len2)
{
for(int i=0;i<len1-len2;++i)
{
ListNode *s = new ListNode(0);
s->next = head2;
head2 = s;
}
}
if(len2 > len1)
{
for(int i=0;i<len2-len1;++i)
{
ListNode *s = new ListNode(0);
s->next = head1;
head1 = s;
}
}
p1 = head1;
p2 = head2;
while(p1 != nullptr)
{
p1->val = p1->val + p2->val;
p1 = p1->next;
p2 = p2->next;
}
int len = len1 > len2 ? len1:len2;
int *arr = new int[len+2];
p1 = head1;
for(int i=len-1;i>=0;--i)
{
arr[i] = p1->val;
// arr[i+1] = arr[i+1] + arr[i]/10;
// arr[i] = arr[i]%10;
p1 = p1->next;
}
for(int i=0;i<len;++i)
{
arr[i+1] = arr[i+1] + arr[i]/10;
arr[i] = arr[i]%10;
}
ListNode *ans = nullptr;
ListNode *p = nullptr;
if(arr[len] > 0)
{
ListNode *s = new ListNode(arr[len]);
s->next = nullptr;
ans = s;
p = s;
}
for(int k=len-1;k>=0;--k)
{
ListNode *s = new ListNode(arr[k]);
s->next = nullptr;
if(ans == nullptr)
{
ans = s;
p = s;
}
else
{
p->next = s;
p = p->next;
}
}
delete []arr;
return ans;
}
};
边栏推荐
- labelme-5.0.1版本编辑多边形闪退
- 阿里云贾朝辉:云XR平台支持彼真科技呈现国风科幻虚拟演唱会
- win系统下pytorch深度学习环境安装
- MySQL高级指令
- “数据引擎”开启前装规模量产新赛道,「智协慧同」崭露头角
- 这些不可不知的JVM知识,我都用思维导图整理好了
- labelme-屏蔽拖拽的事件
- 文件IO-缓冲区
- Why general company will say "go back messages such as" after the end of the interview, rather than just tell the interviewer the result?
- Likou 215 questions, the Kth largest element in an array
猜你喜欢
随机推荐
Common interview questions for APP UI automation testing, maybe useful~
Live Classroom System 09--Tencent Cloud VOD Management Module (1)
Black cat takes you to learn Makefile Part 11: When the header file a.h changes, how to recompile all the .c files that depend on the header file a.h
高数_复习_第5章:多元函数微分学
RTL8721DM 双频WIFI + 蓝牙5.0 物联网(IoT)应用
黑猫带你学Makefile第13篇:Makefile编译问题合集
win系统下pytorch深度学习环境安装
威纶通触摸屏如何在报警的同时,显示出异常数据的当前值?
自组织是管理者和成员的双向奔赴
C#【必备技能篇】Hex文件转bin文件的代码实现
Shell programming specification and variables
特别的三杯鸡
【开源教程5】疯壳·开源编队无人机-飞控固件烧写
交换机和生成树知识点
使用 Cloudreve 搭建私有云盘
水果沙拉酱
ThreadLocal全面解析(一)
LeetCode每日一题(1573. Number of Ways to Split a String)
如何保护 LDAP 目录服务中的用户安全?
论文解读(g-U-Nets)《Graph U-Nets》