当前位置：首页 > news >正文

复习leetcode第二题：两数相加

news 来源：原创 2024/9/29 13:24:23

本文会给出笔者自己的解答（代码较为冗余，其实就是屎山代码）以及优秀代码的解析

下图是题目

解法1（笔者所使用的办法）：

解题思路：

以下思路是基于示例1（上图）思考的

步骤1：因为该函数只传来了两个链表的首元结点指针，所以我们不难想到可以创建一个新链表来存放两链表相加的内容

步骤2：由于我们最后需要返回新链表的首元结点指针，而新链表不断创建以后，用于创建链表的指针也后移了，因此我们还需要创建一个指针phead，用作最后的函数返回

步骤3：题目给我们的结构体名称为Listnode（在注释行写了），笔者觉得大小写切换太麻烦了，因此这边改成了listnode

步骤4：通过示例1我们也不难发现，我们需要使用循环语句来多次让两个链表的结点内容相加，并存放到新链表中；而循环的退出条件应该是l1链表和l2链表的所有结点的数据全部相加完了，即l1、l2同时为空指针。

上述步骤代码如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode listnode;
listnode* buynode(int x) //用于创建新链表的函数{listnode* newnode = (listnode*)malloc(sizeof(listnode));newnode->val = x;newnode->next = NULL;return newnode;
}//l1首元结点指针      //l2首元结点指针
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) 
{int count=0;listnode* newnode=buynode(0); //创建一个新链表的首元结点，之后每次创建新链表都传0值，因为只有给新链表结点0这个初值才不会影响结果//当然也并不是必须给新链表的结点赋初值，这里只是为了保险起见listnode* phead=newnode;while(l1||l2) //退出条件为两个指针全为空指针{……;}return phead;
}

示例1的情况：

示例1中出现了两数相加等于10的情况，最后l1、l2结点所对应的新链表结点留下来的数据为0，然后把 1这个数值进1位和后续结点数据内容相加，这也就导致了 4+3+1 = 8。但我们不难发现，l1、l2的结点数据相加最大值为18（即使加上1也只有19），因此只有可能把1这个数值进1位，不可能把1以外的数值进1位。

因此我们可以进行一个分支语句，分为了最后l1、l2结点数据相加 大于等于10 和 小于等于9 的两种情况；然后通过一个计数器count，来判断是否需要对后一个结点数据加1

每次相加完，让l1、l2、新链表都往后移动一位

代码如下所示：

        //分为l1+l2 <=9 以及 l1+l2 >=10 两种情况//<=9if((l1->val)+(l2->val)+count<=9) {newnode->val=(l1->val)+(l2->val)+count;count=0;}//>=10else{newnode->val=(l1->val)+(l2->val)+count-10;count=1;}l1=l1->next;l2=l2->next; newnode->next=buynode(0);newnode=newnode->next;

示例2的情况用示例1的代码就能解决，此处不再讲解。

示例3的情况：

该示例告诉我们，l1为空时，l2不一定为空；l2为空时，l1不一定为空。

因此，会有三种情况：分别是l1、l2都不为空，只有l1为空，只有l2为空。此处可以通过三条分支语句来解决。

当l1为空，l2不为空时，把l1继续往后移动一位代码会出错（对空指针进行解引用操作），因此我们需要在不同的分支语句里面对不同情况进行不同的向后移位操作

而当把所有数据相加完，l1、l2都为空的时候，有可能count仍为1（示例3输出里最后会出现一个1的原因），因此我们需要在整个循环语句后，解决这个问题。直接在新链表最后面加上一个结点，且最后一个结点数据域只可能为1（上文已经讲解过只可能为1的原因）

代码如下所示：

        if(l1&&l2) //两指针都非空{//分为l1+l2 <=9 以及 l1+l2 >=10 两种情况//<=9if((l1->val)+(l2->val)+count<=9) {newnode->val=(l1->val)+(l2->val)+count;count=0;}//>=10else{newnode->val=(l1->val)+(l2->val)+count-10;count=1;}l1=l1->next;l2=l2->next; }else if(l1) //l1还不为空的情况{if((l1->val)+count<=9){newnode->val=(l1->val)+count;count=0;}else{newnode->val=(l1->val)+count-10;count=1;}l1=l1->next; //为防止对空指针l2进行解引用操作}    else if(l2) //l2还不为空的情况{if((l2->val)+count<=9){newnode->val=(l2->val)+count;count=0;}else{newnode->val=(l2->val)+count-10;count=1;}l2=l2->next; //为防止对空指针l1进行解引用操作}  if(count==1) //两个指针全都为空但count还是为1，是对示例3的解决{newnode->next=buynode(1); //直接在newnode指针最后面加上一个结点，且最后一个结点数据域只可能为1}

由于新链表一直要创建到l1、l2都为空，那么在循环语句（循环语句退出条件为l1、l2都为空）里的新链表创建就不需要加以限制了呢？

答：如果不加以限制，会出现下图的情况，这是由于在最后一次l1、l2结点数据相加并放入新链表以后，还会再进行一次新链表的结点创建

解决方法：

把新链表的首元结点的创建放在循环语句里面，并且在第一次创建新链表的结点时，把该结点赋给phead，并且所有操作都放在l1、l2结点数据相加之前
在循环语句末尾，给新链表的创建加上一条if语句，当l1、l2全为空指针，不再进行结点创建工作（笔者在此使用的）

        if(l1||l2) //只有两指针还有需要存入的数据再开辟新的空间，如果都已经存放完毕，那么就无需再开辟新的{newnode->next=buynode(0);newnode=newnode->next;}

解法1全部代码展示：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode listnode;
listnode* buynode(int x){listnode* newnode = (listnode*)malloc(sizeof(listnode));newnode->val = x;newnode->next = NULL;return newnode;
}//l1首元结点指针      //l2首元结点指针
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) 
{int count=0;listnode* newnode=buynode(0); //创建一个新链表的首元结点listnode* phead=newnode;while(l1||l2) //退出条件为两个指针全为空{if(l1&&l2) //两指针都非空{//分为l1+l2 <=9 以及 l1+l2 >=10 两种情况//<=9if((l1->val)+(l2->val)+count<=9) {newnode->val=(l1->val)+(l2->val)+count;count=0;}//>=10else{newnode->val=(l1->val)+(l2->val)+count-10;count=1;}l1=l1->next;l2=l2->next; }else if(l1) //l1还不为空的情况{if((l1->val)+count<=9){newnode->val=(l1->val)+count;count=0;}else{newnode->val=(l1->val)+count-10;count=1;}l1=l1->next; //为防止对空指针l2进行解引用操作}    else if(l2) //l2还不为空的情况{if((l2->val)+count<=9){newnode->val=(l2->val)+count;count=0;}else{newnode->val=(l2->val)+count-10;count=1;}l2=l2->next; //为防止对空指针l1进行解引用操作}    if(l1||l2) //只有两指针还有需要存入的数据再开辟新的空间，如果都已经存放完毕，那么就无需再开辟新的{newnode->next=buynode(0);newnode=newnode->next;}}if(count==1) //两个指针全都为空但count还是为1，是对示例3的解决{newnode->next=buynode(1); //直接在newnode指针最后面加上一个结点，且最后一个结点数据域只可能为1}return phead;
}

解法2（优秀代码）：

下面的代码是leetcode官方给的C语言题解，好漂亮的代码！

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {struct ListNode *head = NULL, *tail = NULL;int carry = 0;while (l1 || l2) {int n1 = l1 ? l1->val : 0;int n2 = l2 ? l2->val : 0;int sum = n1 + n2 + carry;if (!head) {head = tail = malloc(sizeof(struct ListNode));tail->val = sum % 10;tail->next = NULL;} else {tail->next = malloc(sizeof(struct ListNode));tail->next->val = sum % 10;tail = tail->next;tail->next = NULL;}carry = sum / 10;if (l1) {l1 = l1->next;}if (l2) {l2 = l2->next;}}if (carry > 0) {tail->next = malloc(sizeof(struct ListNode));tail->next->val = carry;tail->next->next = NULL;}return head;
}

上述代码解释：

官方题解也是通过创建一个新链表，然后解决问题

首先创建了两个指针，一个指向了首元结点（用作返回），一个指向了尾元结点（用作存放数据）；carry和我代码中的count一样，都是保存多出来的那个1的

循环语句退出条件、分支语句的写法此处省略

l1 ? l1->val : 0 --->该操作符的作用：l1不为空指针，就留下l1的值；l1为空指针，就留下0

l2 ? l2->val : 0 --->作用同上

sum：就是l1、l2的结点数据（还有carry）相加后结果

!head：如果头指针为空指针为真（首元结点的创建，和首元结点地址的保留）

sum%10：对10取余

sum/10：整型相除

进行完对新链表的赋值操作以后，让新链表的尾元结点指针指向空指针，等待下一次使用

最后如果carry依旧为1，那么再开辟一个结点空间存放，最后返回head指针