题目名称:两数相加(题目来源于力扣)
前言:
此题被进位问题困扰良久,所以注意看如何解决进位问题.
另外,优化版本的代码将三种情况归于一类值的思考.
希望对困扰此题的友友们有些帮助.
题目介绍:
示例1:
示例2:
解题思路:
1.创建一个带头结点的单链表(头结点为sum),该链表用于存储L1链表与L2链表的和.
2.创建spillnum用于保存进位数.
3.遍历两个链表,将结点中的值相加后存入sum链表:
此时分三种情况考虑:
①:两个链表结点都不为空.
②:L1比较短,此时已经走到NULL了.
③:L2比较短,此时已经走到NULL了.
5.注意,还有一个重要情况,当最后两个数相加后也需要进位时,需要特殊处理.
6.返回头结点的next结点.
进位数说明:
题目要求一个结点只能存个位数,所以需要保留进位数到下一个结点.
算进位数:
这是很基本的数学问题,两数相加,大于10的部分需要进位.
low版本 代码实现:
//创建一个新节点 struct ListNode* newNode(int x) { struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode)); if (newnode == NULL) { printf("申请新的节点失败:\n"); return NULL; } newnode->val = x; newnode->next = NULL; return newnode; } struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){ struct ListNode*sum=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode*sumtail=sum; int spillnum=0; while(l1&&l2)//当两个链表都不为NULL时 { struct ListNode*newnode=newNode((l1->val+l2->val+spillnum)%10); spillnum=(l1->val+l2->val+spillnum)/10; sumtail->next=newnode; sumtail=sumtail->next; l1=l1->next; l2=l2->next; } //一方已经为NULL while(l1) { struct ListNode*newnode=newNode((l1->val+spillnum)%10); spillnum=(l1->val+spillnum)/10; sumtail->next=newnode; sumtail=sumtail->next; l1=l1->next; } while(l2) { struct ListNode*newnode=newNode((l2->val+spillnum)%10); spillnum=(l2->val+spillnum)/10; sumtail->next=newnode; sumtail=sumtail->next; l2=l2->next; } if(spillnum==0) return sum->next; else { struct ListNode*newnode=newNode(spillnum); sumtail->next=newnode; return sum->next; } }
优化点:
①:将三种情况合并处理
如果两个链表只要一方有数据,则表示相加还需要继续.此时为避免空指针(NULL),将短的一方设置为0再与长链表相加.
短的一方不再继续后移(->next),用0代替.
②最后结点进位代码可以更加简洁一些.
优化版本 代码实现:
//创建一个新节点 struct ListNode* newNode(int x) { struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode)); newnode->val = x; newnode->next = NULL; return newnode; } struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){ struct ListNode*sum=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode*sumtail=sum;//通过这个指针遍历sum链表 int spillnum=0;//进位数 while(l1||l2)//当两个链表其中一个还有元素的时候 { //如果一方为空,则将其值设置为0. int data1= l1==NULL ? 0 : l1->val; int data2= l2==NULL ? 0 : l2->val; int sum=(data1+data2+spillnum);//两数之和+进位数 struct ListNode*newnode=newNode(sum%10); spillnum=sum/10;//处理进位 //为sum链表新增结点 sumtail->next=newnode; sumtail=sumtail->next; if(l1)//如果L1不是NULL,则后移. l1=l1->next; if(l2)//如果L2不是NULL,则后移. l2=l2->next; } //最后一个结点也可能要进位 if(spillnum!=0)//如果进位数不是0,说明最后一次相加需要进位 { struct ListNode*newnode=newNode(spillnum); sumtail->next=newnode; } return sum->next; }
