假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
数据范围：
，链表任意值 
要求：空间复杂度)
，时间复杂度
要求：空间复杂度
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
[编程题]链表相加(二)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
#include <stdlib.h>
int lenth(struct ListNode* p){
int num =0;
while(p != NULL){
num++;
p = p->next;
}
return num;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
// write code here
int len1, len2, i, j, min = 0;
len1 = lenth(head1);
len2 = lenth(head2);
int* addend1 = (int*)calloc(len1, sizeof(int));
int* addend2 = (int*)calloc(len2, sizeof(int));
int* sum = (int*)calloc(len1+len2, sizeof(int));
struct ListNode* p1 = head1, *p2 = head2;
//将两个加数放入对应数组
for(i = len1 - 1; i >= 0; i--){
addend1[i] = p1->val;
p1 = p1->next;
}
for(i = len2 - 1; i >= 0; i--){
addend2[i] = p2->val;
p2 = p2->next;
}
p1 = head1;
p2 = head2;
//合并两个链表
while(p1->next != NULL){
p1 = p1->next;
}
p1->next = p2;
p1 = head1;
//单个计算对应位加和放入sum数组
if(len1 <= len2){
min = len1;
}else{
min = len2;
}
for(i = 0; i < min; i++){
sum[i] = addend1[i] + addend2[i];
}
j = i;
while(j != len1){
sum[j] = addend1[j];
j++;
}
j = i;
while(j != len2){
sum[j] = addend2[j];
j++;
}
//遍历数组，若发现本位和/10 == 1 说明有进位flag，默认没有进位
int flag = 0;
for(i = 0; i < len1 + len2; i++){
sum[i] += flag;
if(sum[i] / 10 == 1){
flag = 1;
sum[i] = sum[i] % 10;
}else{
flag = 0;
}
}
int dir = 0;//第一个不为0的位置（从0开始）
i = len1 + len2 -1;
while(i >= 0){
if(sum[i] == 0){
i--;
}else{
dir = i;
break;
}
}
i = dir;
while(i >= 0){
p1->val = sum[i];
if(i == 0){
p1->next = NULL;
}else{
p1 = p1->next;
}
i--;
}
return head1;
}
编辑于 2024-04-08 13:27:53
回复(0)
struct ListNode* ReverseList(struct ListNode* head ) {
struct ListNode *p,*res;
if((head==NULL) || (head->next==NULL))
return head;
p = head->next;
res = ReverseList(p);
p->next = head;
p->next->next = NULL;
return res;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
struct ListNode *p,*p1,*p2,*res=NULL;
int carry=0;
p1 = ReverseList(head1);
p2 = ReverseList(head2);
while(p1!=NULL || p2!=NULL) {
int t;
t = (p1==NULL?0:p1->val)+(p2==NULL?0:p2->val)+carry;
if(t>9) {
carry = t/10;
t %= 10;
}
else
carry = 0;
if(res==NULL) {
res = (struct ListNode *)malloc(sizeof(struct ListNode));
res->val = t;
res->next = NULL;
p = res;
}
else {
struct ListNode *NewNode;
NewNode = (struct ListNode *)malloc(sizeof(struct ListNode));
NewNode->val = t;
NewNode->next = NULL;
p->next = NewNode;
p = p->next;
}
if(p1!=NULL)
p1 = p1->next;
if(p2!=NULL)
p2 = p2->next;
};
res = ReverseList(res);
return res;
}
编辑于 2024-03-15 18:01:27
回复(0)
先将两个链表反转，从低位向高位加，用int类型的值表示需要进位的值，先将锻炼表遍历完全后，再把长链表遍历一遍，因为长链表遍历最后一个数据的时候无法确定是否还有进位，所以用if else处理有无进位的方法，在返回值类型中 我觉得把前面得到的链表反转一下
struct ListNode*Reverse(struct ListNode* cur,struct ListNode*prev)
{
if(cur==NULL)return prev;
struct ListNode *temp=NULL;
temp=cur->next;
cur->next=prev;
return Reverse(temp,cur);
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
// write code here
struct ListNode*p1=Reverse(head1,NULL);
struct ListNode*p2=Reverse(head2,NULL);
struct ListNode*ret=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode*p=ret;
int count=0;
while(p1!=NULL && p2!=NULL)
{
int temp=p1->val+p2->val+count;
p1->val=p1->val+p2->val+count;
if(p1->val>=10)
{
p1->val=p1->val-10;
}
count=temp/10;
ret->next=p1;
ret=ret->next;
p1=p1->next;
p2=p2->next;
}
struct ListNode* p3=p1?p1:p2;
while(p3!=NULL)
{
int temp=p3->val+count;
p3->val=p3->val+count;
if(p3->val>=10)
{
p3->val=p3->val-10;
}
count=temp/10;
ret->next=p3;
p3=p3->next;
ret=ret->next;
}
//缺少考虑count会带出来一个进位
struct ListNode*retu=NULL;
if(1==count)
{
struct ListNode*temp1=p->next;
struct ListNode*temp2=Reverse(temp1,NULL);
p->val=count;
p->next=temp2;
retu=p;
}
else { //count没有进位的情况
struct ListNode*temp1=p->next;
struct ListNode*temp2=Reverse(temp1,NULL);
retu=temp2;
}
return retu;
}
编辑于 2024-03-10 17:58:13
回复(0)
先反转链表，定义一个int型的值表示进位，然后两个链表同进位逐个相加，申请一个新节点保持得到的值，用头插法连接起来。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
struct ListNode* ReverseList(struct ListNode* head ) {
if (head == NULL) {
return NULL;
}
struct ListNode* next = NULL;
struct ListNode* prior = NULL;
while (head != NULL){
next = head->next;//保存下一个节点
//头插法
head->next = prior;
prior = head;
head = next;
}
return prior ;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
// write code here
struct ListNode* p1 = ReverseList(head1);
struct ListNode* p2 = ReverseList(head2);
struct ListNode* res = NULL;
struct ListNode* p = NULL;
int i =0;
while (p1!=NULL&&p2!=NULL) {
p = (struct ListNode*)malloc(sizeof(struct ListNode));
p->next = res;
if (p1->val+p2->val+i >= 10) {
p->val = p1->val+p2->val+i-10;
i = 1;
}else {
p->val = p1->val+p2->val+i;
i = 0;
}
res = p;
p1 = p1->next;
p2 = p2->next;
}
p = NULL;
while (p1!=NULL) {
if (p1->val+i>=10) {
p1->val = p1->val+i-10;
i=1;
}else {
p1->val = p1->val+i;
i = 0;
}
p = p1->next;
p1->next = res;
res = p1;
p1 = p;
}
while (p2!=NULL) {
if (p2->val+i>=10) {
p2->val = p2->val+i-10;
i=1;
}else {
p2->val = p2->val+i;
i = 0;
}
p = p2->next;
p2->next = res;
res = p2;
p2 = p;
}
if (i==1) {
p = (struct ListNode*)malloc(sizeof(struct ListNode));
p->val = 1;
p->next = res;
res = p;
}
return res;
}
编辑于 2024-02-07 18:27:35
回复(0)
超级耗内存的递归。。
#include <stdio.h>
#include <stdlib.h>
int ListLen(struct ListNode* p){
int rtn = 0;
while(p!=NULL){
rtn = rtn+1;
p = p->next;
}
return rtn;
}
bool ListAdd(struct ListNode* ans,struct ListNode* p1,struct ListNode* p2, int len1,int len2){
bool upper = false;
if(ans!=NULL){
if(len1>=0){
ans->val += p1->val;
p1 = p1->next;
}
if(len2>=0){
ans->val += p2->val;
p2 = p2->next;
}
if(ListAdd(ans->next,p1,p2,len1+1,len2+1)){
ans->val+=1;
}
if(ans->val>=10){
ans->val -=10;
return true;
}
}
return false;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
// write code here
struct ListNode* rtn = malloc(sizeof(struct ListNode)*1);
struct ListNode* tmp;
int len1 = ListLen(head1);
int len2 = ListLen(head2);
int i,rlen;
rlen = len1>len2?len1:len2;
rtn->val = 0;
rtn->next = NULL;
tmp = rtn;
for(i = 0;i < rlen;i++){
tmp->next = malloc(sizeof(struct ListNode));
tmp = tmp->next;
tmp->val = 0;
tmp->next = NULL;
}
ListAdd(rtn,head1,head2,len1-rlen-1,len2-rlen-1);
if(rtn->val == 0){
return rtn->next;
}
return rtn;
}
发表于 2023-09-14 15:22:02
回复(0)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
//编写翻转链表的函数
struct ListNode* reverse(struct ListNode* head)
{
if(head==NULL||head->next==NULL)
{
return head;
}
struct ListNode* n1,*n2,*n3;
n1=NULL,n2=head,n3=head->next;
while(n2!=NULL)
{
n2->next=n1;
n1=n2;
n2=n3;
if(n3)
{
n3=n3->next;
}
}
return n1;
// struct ListNode* newnode;
// newnode=reverse(head->next);
// head->next->next=head;
// head->next=NULL;
// return newnode;
}
//编写计算链表长度的函数
int get_len(struct ListNode* head)
{
int len=0;
while(head)
{
len++;
head=head->next;
}
return len;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
if(head1==NULL)
return head2;
if(head2==NULL)
return head1;
struct ListNode* phead1,*phead2;
phead1=reverse(head1);
phead2=reverse(head2);
int len1=get_len(head1);
int len2=get_len(head2);
struct ListNode* plist1=phead1;
struct ListNode* plist2=phead2;
if(len1<len2)
{
plist1=phead2;
plist2=phead1;
}
int arr_j=0;
int arr_b=0;
struct ListNode* phead=NULL;
phead=plist1;
while(plist2)
{
plist1->val=plist1->val+arr_j;
arr_b=plist1->val+plist2->val;
plist1->val=arr_b%10;
arr_j=arr_b/10;
plist1=plist1->next;
plist2=plist2->next;
}
if(arr_j==1)
{
while(plist1)
{
arr_b=plist1->val+arr_j;
plist1->val=arr_b%10;
arr_j=arr_b/10;
plist1=plist1->next;
}
}
struct ListNode* ret=reverse(phead);
if(arr_j==1)
{
struct ListNode* newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
newnode->val=1;
newnode->next=ret;
ret=newnode;
}
return ret;
}
发表于 2023-08-22 21:36:09
回复(0)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
struct ListNode* ReverseList(struct ListNode* pHead );
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
// write code here
int i = 0;
struct ListNode *Head1 = ReverseList(head1);
struct ListNode *Head2 = ReverseList(head2);
struct ListNode *p = (struct ListNode *)malloc( sizeof(struct ListNode) );
struct ListNode *n,*Head = p;
p->next=NULL;
while (Head1&&Head2) {
n = (struct ListNode *)malloc( sizeof(struct ListNode) );
if((Head1->val + Head2->val + i)>=10)
{
n->val=(Head1->val + Head2->val + i)-10;
i=1;
}
else
{
n->val=(Head1->val + Head2->val + i);
i=0;
}
n->next=NULL;
p->next=n;
p=n;
Head1 = Head1->next;
Head2 = Head2->next;
}
if (i==0)
{
if (Head1) {
p->next=Head1;
}
else if (Head2){
p->next=Head2;
}
else;
}
while (Head1&&i)
{
n = (struct ListNode *)malloc( sizeof(struct ListNode) );
if((Head1->val + i)>=10)
{
n->val=(Head1->val + i)-10;
i=1;
n->next=NULL;
p->next=n;
p=n;
Head1 = Head1->next;
}
else
{
n->val=(Head1->val + i);
i=0;
p->next=n;
p=n;
p->next=Head1->next;
}
}
while (Head2&&i)
{
n = (struct ListNode *)malloc( sizeof(struct ListNode) );
if((Head2->val + i)>=10)
{
n->val=(Head2->val + i)-10;
i=1;
n->next=NULL;
p->next = n;
p = n;
Head2 = Head2->next;
}
else
{
n->val=(Head2->val + i);
i=0;
p->next=n;
p=n;
p->next=Head2->next;
}
}
if (i==1) {
n = (struct ListNode *)malloc( sizeof(struct ListNode) );
n->val=1;
n->next=NULL;
p->next = n;
p = n;
}
return ReverseList(Head->next);
}
struct ListNode* ReverseList(struct ListNode* pHead )
{
// write code here
if(pHead==NULL||pHead->next==NULL){
return pHead;
}
struct ListNode *cur = NULL;
cur = pHead;
struct ListNode *pre = NULL;
struct ListNode *temp;
while (cur) {
temp = cur->next;
cur->next=pre;
pre = cur;
cur = temp;
}
return pre;
}
发表于 2023-05-26 13:52:40
回复(0)
变量超了范围，仅供参考
#include <stdio.h>
//翻转链表
struct ListNode* reverse(struct ListNode* head){
struct ListNode* cur = head;
struct ListNode* pre = NULL;
struct ListNode* nex = head->next;
while(cur)
{
cur->next = pre;
pre = cur;
cur = nex;
nex = cur->next;
}
return pre;
}
//链表相加
struct ListNode* addTwoNumbers(struct ListNode* head1, struct ListNode* head2){
struct ListNode* l1 = head1;
struct ListNode* l2 = head2;
struct ListNode* tail;
int n = 1;
int sum = 0;
while (l1 && l2) {
sum += (l1->val + l2->val) * n;
l1=l1->next;
l2=l2->next;
n=n*10;
}
while (l1==NULL && l2!=NULL) {
sum += l2->val * n;
l2=l2->next;
n=n*10;
}
while (l1!=NULL && l2==NULL) {
sum += l1->val * n;
l1=l1->next;
n=n*10;
}
// 头指针c
struct ListNode* c = NULL;
while (sum>=1) {
struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
p->val = sum % 10;
p->next = c;
c = p;
sum = sum/10;
}
return c;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
// write code here
if (head1->val==0) {
return head2;
}
if (head2->val==0) {
return head1;
}
if (head1->next) {
head1 = reverse(head1);
}
if (head2->next) {
head2 = reverse(head2);
}
struct ListNode* head3;
head3 = addTwoNumbers(head1, head2);
return head3;
}
发表于 2023-05-25 15:18:34
回复(0)
先链表反转，每位判断相加，头插法建立新链表
#include <stdlib.h>
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
// write code here
struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* q = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* tmp;
int sum = 0; //当前位
int flage = 0; //进位符号位
head->next = NULL;
p->next = NULL;
q->next = NULL;
//头插法逆置两个链表
while (head1 != NULL)
{
tmp = head1;
head1 = head1->next;
tmp->next = p->next;
p->next = tmp;
}
p = p->next;
while (head2 != NULL)
{
tmp = head2;
head2 = head2->next;
tmp->next = q->next;
q->next = tmp;
}
q = q->next;
while (1)
{
if(q != NULL && p != NULL)
{
sum = q->val + p->val + flage; //低位 符号位 相加
flage = sum >= 10 ? 1 : 0; //判断是否进位
sum %= 10; //进位后
p = p->next;
q = q->next;
}
else if (q != NULL && p == NULL)
{
sum = q->val + flage;
flage = sum >= 10 ? 1 : 0;
sum %= 10;
q = q->next;
}
else if (q == NULL && p != NULL)
{
sum = p->val + flage;
flage = sum >= 10 ? 1 : 0;
sum %= 10;
p = p->next;
}
else if(q == NULL && p == NULL && flage == 1)
{
sum = 1; //最高位只有进位
flage = 0;
}
else
{
break;
}
//头插法插入 每一位的结果sum
struct ListNode* new = (struct ListNode*)malloc(sizeof(struct ListNode));
new->val = sum;
new->next = head->next;
head->next = new;
}
return head->next;
}
发表于 2023-04-04 20:21:52
回复(0)
使用逆置的一种方法
struct ListNode* reverse(struct ListNode* head){
struct ListNode* p1 = head->next;
struct ListNode* p2 = p1->next;
head->next = NULL;
while(p1){
p1->next = head;
head = p1;
p1 = p2;
if(p1)
p2 = p1->next;
}
return head;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode* head1 = l1;
struct ListNode* head2 = l2;
struct ListNode* tail;
while(head1 && head2){
tail = head1;
head1->val = head1->val + head2->val;
if(head1->val >= 10 && head1->next){
head1->val %= 10;
head1->next->val++;
}
else if(head1->val >= 10 && head2->next){
head1->val %= 10;
head2->next->val++;
head1->next = head2->next;
head2->next = NULL;
}
else if(head1->val >= 10){
head1->val %= 10;
l2->val = 1;
tail->next = l2;
l2->next = NULL;
}
head1 = head1->next;
head2 = head2->next;
}
while(head1){
if(head1->val >= 10){
head1->val %= 10;
if(head1->next)
head1->next->val++;
else{
l2->val = 1;
head1->next = l2;
l2->next = NULL;
}
}
head1 = head1->next;
}
while(head2)
{
tail->next = head2;
head2 = NULL;
}
return l1;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ){
if(head1->val == 0)
return head2;
if(head2->val == 0)
return head1;
if(head1->next)
head1 = reverse(head1);//逆置
if(head2->next)
head2 = reverse(head2);//逆置
struct ListNode* head3;
head3 = addTwoNumbers(head1, head2);//相加
if(head3->next)
head3 = reverse(head3);//结果逆置回来
return head3;
}
发表于 2023-02-08 14:13:11
回复(0)
一种比较传统的做法
typedef struct ListNode* pnode;
// 将两个链表的值求和
void mycombine(pnode head1,pnode head2,int len1,int len2){
pnode p=head1;
pnode q=head2;
while(len1>len2){
p=p->next;
len1--;
}//保持后对齐
while(p){
p->val+=q->val;
p=p->next;
q=q->next;
}
}
int carrybit(pnode head){ //实现进位操作
if(head==NULL)return 0;
head->val+=carrybit(head->next);
if(head->val>=10){
head->val-=10;
return 1;
}else return 0;
}
int mystrlen(pnode head){//计算链表得长度
int count=0;
while(head){
head=head->next;
count++;
}
return count;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
if(head1==NULL) return head1;
if(head2==NULL) return head2;
int len1=mystrlen(head1);
int len2=mystrlen(head2);
pnode temp=NULL;
//找到较大的链表，求和得到的放入其中；
if(len1>=len2){
temp=head1;
mycombine(temp,head2,len1,len2);//两个链表的值加到temp里
}else{
temp=head2;
mycombine(temp,head1,len2,len1);//两个链表的值加到temp里
}
int i=carrybit(temp);
if(i==1){
pnode newhead=(pnode)malloc(sizeof(struct ListNode));
newhead->val=1;
newhead->next=temp;
temp=newhead;
}
return temp;
}
发表于 2022-11-25 23:09:02
回复(0)
struct ListNode* ReverseList(struct ListNode* pHead )
{
struct ListNode *p = pHead;
struct ListNode *q = NULL;
struct ListNode *temp = NULL;
while(p)
{
temp = q;
q = p;
p = p->next;
q->next = temp;
}
// write code here
return q;
}
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 )
{
struct ListNode *p = ReverseList(head1);
struct ListNode *newhead = p;
struct ListNode *q = ReverseList(head2);
struct ListNode *temp = NULL;
int jin = 0;
while(p && q)
{
if(p->val + q->val + jin <= 9)
{
p->val = p->val + q->val + jin;
jin = 0;
}
else
{
p->val = (p->val + q->val +jin)%10;
jin = 1;
}
temp = p;
p = p->next;
q = q->next;
}
while(p || q || jin)
{
if(p)
{
if(p->val +jin <= 9)
{
p->val = p->val +jin;
jin = 0;
}
else
{
p->val = 0;
jin = 1;
}
temp = p;
p = p->next;
}
else if(q)
{
struct ListNode * newp = (struct ListNode *)malloc(sizeof(struct ListNode));
temp->next = newp; // 最后一个结点的下一个 是 新结点
newp->next = NULL;
if(q->val +jin <= 9)
{
newp->val = q->val +jin;
jin = 0;
}
else
{
newp->val = 0;
jin = 1;
}
temp = newp;
q = q->next;
}
else if(jin)
{
struct ListNode * newp = (struct ListNode *)malloc(sizeof(struct ListNode));
temp->next = newp; // 最后一个结点的下一个 是 新结点
newp->next = NULL;
newp->val = jin;
jin = 0;
}
}
return ReverseList(newhead);
// write code here
}
发表于 2022-11-02 21:15:20
回复(0)
struct ListNode *reverse(struct ListNode *head)
{
if(head == NULL || head->next == NULL)
return head;
struct ListNode * newhead = NULL;
struct ListNode * next = NULL;
while(head != NULL)
{
next = head->next;
head->next = newhead;
newhead = head;
head = next;
}
return newhead;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
if(head1 == NULL && head2 == NULL)
return NULL;
struct ListNode * revhead1 = NULL,*Head1 = NULL;
struct ListNode * revhead2 = NULL,*Head2 = NULL;
//翻转链表
revhead1 = reverse(head1);
Head1 = revhead1;
revhead2 = reverse(head2);
Head2 = revhead2;
struct ListNode * list = (struct ListNode *)malloc(sizeof(struct ListNode));
list->next = NULL;
//进位
int carry = 0;
//head1 与head2 val相加的数值
int temp = 0;
//考虑进位后要在节点存储的值
int data = 0;
while(revhead1 != NULL || revhead2 != NULL || carry != 0)
{
//revehead1 不为空
if(revhead1)
{
temp = temp + revhead1->val;
revhead1 = revhead1->next;
}
//revhead2 不为空
if(revhead2)
{
temp = temp + revhead2->val;
revhead2 = revhead2->next;
}
data = (temp+carry)%10;
//创建节点
struct ListNode * pnode = (struct ListNode *)malloc(sizeof(struct ListNode));
//使用头插法，插入节点
pnode->val = data;
pnode->next = list->next;
list->next = pnode;
carry = (temp+carry)/10;
temp = 0;
}
//记得把链表翻转回去
head1 = reverse(Head1);
head2 = reverse(Head2);
return list->next;
}
发表于 2022-10-27 18:26:07
回复(0)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
//思想：逆置相加，最后逆置输出
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
struct ListNode* p1front=NULL;
struct ListNode* p1next;
struct ListNode* p2front=NULL;
struct ListNode* p2next;
struct ListNode* addp1;
struct ListNode* addp2;
struct ListNode* addp;
struct ListNode* New;
struct ListNode* lens;
int len1=0;
int len2=0;
int temp1=0;
lens=head1;
while(lens){//head1长
len1++;
lens=lens->next;
}
lens=head2;
while(lens){//head2长
len2++;
lens=lens->next;
}
while(head1){//逆置head1
p1next=head1->next;
head1->next=p1front;
p1front=head1;
head1=p1next;
}
while(head2){//逆置head2
p2next=head2->next;
head2->next=p2front;
p2front=head2;
head2=p2next;
}
addp1=p1front;
addp2=p2front;
while(addp1&&addp2){//对应位置值相加
temp1=addp1->val+addp2->val;
addp1->val=temp1;
addp2->val=temp1;
addp1=addp1->next;
addp2=addp2->next;
}
if(len1>len2){//哪个链表长就将指针赋给谁
addp=p1front;
}else{
addp=p2front;
}
while(addp){//后续有节点-对应位置值大于9则进1，无节点-创建新节点
if(addp->val>9){//值大于9
addp->val=addp->val%10;
if(!addp->next){//后续无节点
New=(struct ListNode*)malloc(sizeof(struct ListNode));
New->val=1;
New->next=NULL;
addp->next=New;
addp=New;
}else{//有节点
addp->next->val=addp->next->val+1;
}
}//值小于10则不做操作，指针后移
addp=addp->next;
}
head1=NULL;
if(len1>len2){//将链表最长的，逆置
while(p1front){
p1next=p1front->next;
p1front->next=head1;
head1=p1front;
p1front=p1next;
}
}else{
while(p2front){
p1next=p2front->next;
p2front->next=head1;
head1=p2front;
p2front=p1next;
}
}
return head1;
// write code here
}
发表于 2022-10-22 19:31:42
回复(0)
递归求解加法以及进位:
int Recursion(struct ListNode* head1,struct ListNode* head2,int cout);
int LengthListNode(struct ListNode* pHead);
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2) {
// write code here
int len1=LengthListNode(head1);
int len2=LengthListNode(head2);
int sub=len1>len2?len1-len2:len2-len1;
struct ListNode* nh=(struct ListNode*)malloc(sizeof(struct ListNode));
int cout=0;
if(sub==0){
cout=Recursion(head1,head2,0);;
if(cout!=0){
nh->next=head1;nh->val=cout;
return nh;
}else{
return head1;
}
}
struct ListNode* sp=0;
struct ListNode* ep=0;
while(sub){ //补零序列
ep=(struct ListNode*)malloc(sizeof(struct ListNode));ep->val=0;
ep->next=sp;sp=ep;sub=sub-1;
}
//ep指向零结点的最后结点
ep=sp;
while(ep->next!=0){
ep=ep->next;
}
//连接上长度小的头结点
if(len1>len2){
ep->next=head2;
cout=Recursion(sp,head1,0); //存在sp中
}else{
ep->next=head1;
cout=Recursion(sp,head2,0); //存在sp中
}
//根据cout来进行输出
if(cout!=0){ //存在进位
nh->val=cout;nh->next=sp;
return nh;
}else{ //不存在进位
return sp;
}
}
int LengthListNode(struct ListNode* pHead){
int data=0;
while(pHead!=0){
pHead=pHead->next;data++;
}
return data;
}
int Recursion(struct ListNode* head1,struct ListNode* head2,int cout){
if(head1->next==0&&head2->next==0){
int result=head1->val+head2->val+cout;
head1->val=result%10;
return result/10;
}
int ct=Recursion(head1->next,head2->next,cout);
int result=head1->val+head2->val+ct;
head1->val=result%10;
return result/10;
}
发表于 2022-08-19 11:50:15
回复(0)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
#先反转链表，再竖式相加
#include<stdlib.h>
struct ListNode * reverseListnode(struct ListNode *head)
{
struct ListNode *p, *q, *temp;
if(head ==NULL) return NULL;
if(head->next == NULL) return head;
p = head;
q = head->next;
head->next = NULL;
while(q != NULL)
{
temp = q->next;
q->next = p;
p = q;
q = temp;
}
return p;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
// write code here
if(head1 == NULL && head2 == NULL) return NULL;
struct ListNode *tail1, *tail2;
tail1 = reverseListnode(head1);
tail2 = reverseListnode(head2);
int flag=0;
struct ListNode *p, *q, *head, *temp;
p = tail1;
q = tail2;
temp = NULL;
while(p != NULL && q != NULL)
{
head = (struct ListNode *) malloc(sizeof(struct ListNode));
head->val = p->val + q->val;
if(flag)
{
head->val ++;
flag = 0;
}
if(head->val > 9)
{
head->val = head ->val -10;
flag = 1;
}
head->next = temp;
temp = head;
p = p->next;
q = q->next;
}
while(p != NULL)
{
head = (struct ListNode *) malloc(sizeof(struct ListNode));
head->val = p->val;
if(flag)
{
head->val ++;
flag = 0;
}
if(head->val > 9)
{
head->val = head ->val -10;
flag = 1;
}
head->next = temp;
temp = head;
p = p->next;
}
while(q != NULL)
{
head = (struct ListNode *) malloc(sizeof(struct ListNode));
head->val = q->val;
if(flag)
{
head->val ++;
flag = 0;
}
if(head->val > 9)
{
head->val = head ->val -10;
flag = 1;
}
head->next = temp;
temp = head;
q = q->next;
}
if(flag)
{
head = (struct ListNode *) malloc(sizeof(struct ListNode));
head->val = 1;
head->next = temp;
}
tail1->next = NULL;
tail2->next = NULL;
return head;
}
发表于 2022-03-04 11:43:28
回复(0)
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) { //相加是从低位向高位进位 设置一个进位表示CFlag //用头插法改变读取顺序 再在第二次复原时使用头插法恢复 int i,j,k; struct ListNode *p1,*p2,*head3,*newnode,*work1,*work2; int Cflag=0; i=0;j=0; p1=head1;p2=head2; while(p1!=NULL){ i++;p1=p1->next; } while(p2!=NULL){ j++;p2=p2->next; } p1=head1;p2=head2; head3=NULL; newnode=(struct ListNode*)malloc(sizeof(struct ListNode)); if(i>j){ k=i-j; while(k!=0){ newnode->val=p1->val; p1=p1->next; newnode->next=head3; head3=newnode; newnode=(struct ListNode*)malloc(sizeof(struct ListNode)); k--; }} if(j>i){ k=j-i; while(k!=0){ newnode->val=p2->val; p2=p2->next; newnode->next=head3; head3=newnode; newnode=(struct ListNode*)malloc(sizeof(struct ListNode)); k--; }} while(p1&&p2){ newnode->val=p1->val+p2->val; newnode->next=head3; head3=newnode; newnode=(struct ListNode*)malloc(sizeof(struct ListNode)); p1=p1->next;p2=p2->next; } //逆置的链表生成了 使用Cflag记录进位 使用头插再次逆置； work1=head3; head3=NULL; while(work1){ if(Cflag==1){ work1->val+=1; Cflag=0; } if(work1->val>9){ work1->val=work1->val%10; Cflag=1; } work2=work1->next; work1->next=head3; head3=work1; work1=work2; } if(Cflag){ newnode->val=1; newnode->next=head3; head3=newnode; } return head3; }
发表于 2021-10-12 21:45:35
回复(0)
问题信息
难度：
25条回答
980收藏
9942浏览
通过挑战的用户
查看代码-
2023-03-08 10:33:10 -
2023-02-04 19:27:02
-
2023-01-30 11:11:51
-
2023-01-20 01:16:08 -
2022-12-24 16:12:23
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
