力扣---两数相加(c语言版)_C/C++

在这里插入图片描述

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

[传送门]

前言:

此题被进位问题困扰良久,所以注意看如何解决进位问题.
另外,优化版本的代码将三种情况归于一类值的思考.
希望对困扰此题的友友们有些帮助.

一、题目介绍:

示例1:

在这里插入图片描述

示例2:

示例3:

二、解题思路分析:

进位数说明:

题目要求一个结点只能存个位数,所以需要保留进位数到下一个结点.

算进位数:
这是很基本的数学问题,两数相加,大于10的部分需要进位.
在这里插入图片描述

2.1 代码实现(low版本 ):

/**
 * definition for singly-linked list.
 * struct listnode {
 *     int val;
 *     struct listnode *next;
 * };
 */
//创建一个新节点
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代替.

②最后结点进位代码可以更加简洁一些.

2.2 代码实现(优化版本):

/**
 * definition for singly-linked list.
 * struct listnode {
 *     int val;
 *     struct listnode *next;
 * };
 */
//创建一个新节点
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;
}