题目名称:两数相加(题目来源于力扣)

[传送门]

前言:

此题被进位问题困扰良久,所以注意看如何解决进位问题.

另外,优化版本的代码将三种情况归于一类值的思考.

希望对困扰此题的友友们有些帮助.

题目介绍:

示例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; }