当前位置:网站首页>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;
}
};
边栏推荐
- 水果沙拉酱
- c语言之 练习题1 大贤者福尔:魔法数,神奇的等式
- What are the concepts, purposes, processes, and testing methods of interface testing?
- How to secure users in LDAP directory service?
- 华为HCIE云计算之Fusion Access桌面云
- Black cat takes you to learn Makefile Part 12: Summary of common Makefile problems
- Extended Chinese Remainder Theorem
- 今日睡眠质量记录75分
- JVM classic fifty questions, now the interview is stable
- Use Cloudreve to build a private cloud disk
猜你喜欢
Redis Performance Impact - Asynchronous Mechanisms and Response Latency
APP UI自动化测试常见面试题,或许有用呢~
Shell编程之条件语句(二)
链表中的节点每k个一组翻转
HighTec shortcut keys (Keys) setting location
服务——DNS正向反向域名解析服务
接口测试的概念、目的、流程、测试方法有哪些?
基于交流潮流的电力系统多元件N-k故障模型研究(Matlab代码实现)【电力系统故障】
交换机和生成树知识点
[SQL brush questions] Day3----Special exercises for common functions that SQL must know
随机推荐
An article to teach you a quick start and basic explanation of Pytest, be sure to read
MySQL Advanced Commands
解码2022中国网安强星丨正向建、反向查,华为构建数字化时代的网络安全防线
camera预览流程 --- 从HAL到OEM
camera preview process --- from HAL to OEM
【PCBA scheme design】Bluetooth skipping scheme
MySQL高级指令
shell脚本循环语句for、while语句
商家招募电商主播要考虑哪些内容
Regular expression of shell programming and text processor
这些不可不知的JVM知识,我都用思维导图整理好了
Redis Performance Impact - Asynchronous Mechanisms and Response Latency
ThreadLocal全面解析(一)
QT笔记——QT工具uic,rcc,moc,qmake的使用和介绍
JVM classic fifty questions, now the interview is stable
IM 即时通讯开发如何设计图片文件的服务端存储架构
[Maui official version] Create a cross-platform Maui program, as well as the implementation and demonstration of dependency injection and MVVM two-way binding
ASCII、Unicode和UTF-8
Thread State 详解
2022.8.9 Mock Competition