NC317. 链表相加(一)
描述
示例1
输入:
{2,5,6},{5,6,1}
输出:
{7,1,8}
示例2
输入:
{0},{1,2,3,4,5,6}
输出:
{1,2,3,4,5,6}
示例3
输入:
{9,9,9},{9,9,0}
输出:
{8,9,0,1}
C++ 解法, 执行用时: 313ms, 内存消耗: 76752KB, 提交时间: 2022-06-21
class Solution {
public:
ListNode* ListAdd(ListNode* l1, ListNode* l2) {
ListNode* a = l1;
ListNode* b = l2;
ListNode* c = a;
int f = 0;
while (a && b) {
int k = a->val + b->val + f;
if (k > 9) {
a->val = k - 10;
f = 1;
} else {
a->val = k;
f = 0;
}
c = a;
a = a->next;
b = b->next;
}
if (b) {
c->next = b;
a = b;
}
while (a) {
int k = a->val + f;
if (k > 9) {
a->val = k - 10;
f = 1;
} else {
a->val = k;
f = 0;
}
c = a;
a = a->next;
}
if (f) {
c->next = new ListNode(1);
}
return l1;
}
};
C++ 解法, 执行用时: 319ms, 内存消耗: 76868KB, 提交时间: 2022-03-03
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param l1 ListNode类
* @param l2 ListNode类
* @return ListNode类
*/
ListNode* ListAdd(ListNode* l1, ListNode* l2) {
// write code here
ListNode* p1 = l1;
ListNode* p2 = l2;
ListNode* lastNode = p1;
int carry = 0;
while(p1 && p2)
{
int digit = p1->val + p2->val + carry;
if(digit>9)
{
p1->val = digit - 10;
carry = 1;
}
else
{
p1->val = digit;
carry = 0;
}
lastNode = p1;
p1 = p1->next;
p2 = p2->next;
}
if(p2)
{
lastNode->next = p2;
p1 = p2;
}
while(p1)
{
int digit = p1->val + carry;
if(digit>9)
{
p1->val = digit - 10;
carry = 1;
}
else
{
p1->val = digit;
carry = 0;
}
lastNode = p1;
p1 = p1->next;
}
if(carry)
{
lastNode->next = new ListNode(1);
}
return l1;
}
};
C++ 解法, 执行用时: 320ms, 内存消耗: 76836KB, 提交时间: 2022-03-29
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param l1 ListNode类
* @param l2 ListNode类
* @return ListNode类
*/
ListNode* ListAdd(ListNode* l1, ListNode* l2) {
// write code here
ListNode*p = l1;
ListNode*q = l2;
int sum=0;
while(p->next&&q->next){
sum = p->val+q->val+sum;
p->val = sum%10;
sum = sum/10;
p = p->next;
q = q->next;
}
sum = p->val+q->val+sum;
p->val = sum%10;
sum = sum/10;
ListNode*r;
if(p->next!=nullptr){
r = p;
}else{
r = q;
p->next = q->next;}
while(r->next){
r = r->next;
sum = sum+r->val;
r->val = sum%10;
sum = sum/10;
}
if(sum>0){
ListNode*s = new ListNode(0);
s->val = sum;
s->next = nullptr;
r->next = s;
}
return l1;
}
};
C++ 解法, 执行用时: 337ms, 内存消耗: 76752KB, 提交时间: 2022-08-06
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param l1 ListNode类
* @param l2 ListNode类
* @return ListNode类
*/
ListNode* ListAdd(ListNode* l1, ListNode* l2) {
// write code here
ListNode *a=l1;
ListNode *b=l2;
ListNode *c=a;
int f=0;
while(a&&b)
{
int k=a->val+b->val+f;
if(k>9)
{
a->val=k-10;
f=1;
}else{
a->val=k;
f=0;
}
c=a;
a=a->next;
b=b->next;
}
if(b)
{
c->next=b;
a=b;
}
while(a)
{
int k=a->val+f;
if(k>9)
{
a->val=k-10;
f=1;
}else{
a->val=k;
f=0;
}
c=a;
a=a->next;
}
if(f)
{
c->next=new ListNode(1);
}
return l1;
}
};
C++ 解法, 执行用时: 338ms, 内存消耗: 76740KB, 提交时间: 2022-04-12
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param l1 ListNode类
* @param l2 ListNode类
* @return ListNode类
*/
ListNode* ReverseList(ListNode* pHead) {
ListNode* now = pHead;
ListNode* next = nullptr;
ListNode* pre = nullptr;
while (now != nullptr) {
next = now->next;
now->next = pre;
pre = now;
now = next;
}
return pre;//注意要有返回值
}
ListNode* ListAdd(ListNode* head1, ListNode* head2) {
ListNode* p1 = head1;
ListNode* p2 = head2;
ListNode* h1 = p1;
ListNode* h2 = p2;
head1 = p1;
head2 = p2;
while (p1 != nullptr && p2 != nullptr) {
p1->val += p2->val;
p2->val = p1->val;
p1 = p1->next;
p2 = p2->next;
}
int x = 0;
if (p1 != NULL && p2 == NULL) {
while (h1->next != nullptr) {
x = h1->val;
h1->val = (x % 10);
h1->next->val += (x / 10);
h1 = h1->next;
}
if (h1->val >= 10) {
h1->next = new ListNode(int(h1->val / 10));
h1->val %= 10;
}
return head1;
}else{
while (h2->next != nullptr) {
x = h2->val;
h2->val = (x % 10);
h2->next->val += (x / 10);
h2 = h2->next;
}
if (h2->val >= 10) {
h2->next = new ListNode(int(h2->val / 10));
h2->val %= 10;
}
return head2;
}
return 0;
}
};