??個(gè)人主頁:?? :???初階牛???
??推薦專欄: ?????? c語言初階
??個(gè)人信條: ??知行合一
??本篇簡(jiǎn)介:>:記錄一個(gè)力扣寫了好久的一個(gè)問題
金句分享:
?在心里種花,人生才不會(huì)荒蕪!?

題目名稱:兩數(shù)相加(題目來源于力扣)

[傳送門]

前言:

此題被進(jìn)位問題困擾良久,所以注意看如何解決進(jìn)位問題.
另外,優(yōu)化版本的代碼將三種情況歸于一類值的思考.
希望對(duì)困擾此題的友友們有些幫助.

一、題目介紹:

給你兩個(gè) 非空 的鏈表，表示兩個(gè)非負(fù)的整數(shù)。它們每位數(shù)字都是按照 逆序 的方式存儲(chǔ)的，并且每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字。
請(qǐng)你將兩個(gè)數(shù)相加，并以相同形式返回一個(gè)表示和的鏈表。你可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會(huì)以 0 開頭。

示例1:

輸入：l1 = [2,4,3], l2 = [5,6,4]
輸出：[7,0,8]
解釋：342 + 465 = 807.

示例2:

輸入：l1 = [0], l2 = [0]
輸出：[0]

示例3:

輸入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
輸出：[8,9,9,9,0,0,0,1]

二、解題思路分析:

1.創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的單鏈表(頭結(jié)點(diǎn)為sum),該鏈表用于存儲(chǔ)L1鏈表與L2鏈表的和.
2.創(chuàng)建spillnum用于保存進(jìn)位數(shù).
3.遍歷兩個(gè)鏈表,將結(jié)點(diǎn)中的值相加后存入sum鏈表:
此時(shí)分三種情況考慮:
①:兩個(gè)鏈表結(jié)點(diǎn)都不為空.
②:L1比較短,此時(shí)已經(jīng)走到NULL了.
③:L2比較短,此時(shí)已經(jīng)走到NULL了.
5.注意,還有一個(gè)重要情況,當(dāng)最后兩個(gè)數(shù)相加后也需要進(jìn)位時(shí),需要特殊處理.
6.返回頭結(jié)點(diǎn)的next結(jié)點(diǎn).

進(jìn)位數(shù)說明:

題目要求一個(gè)結(jié)點(diǎn)只能存?zhèn)€位數(shù),所以需要保留進(jìn)位數(shù)到下一個(gè)結(jié)點(diǎn).

算進(jìn)位數(shù):
這是很基本的數(shù)學(xué)問題,兩數(shù)相加,大于10的部分需要進(jìn)位.

2.1 代碼實(shí)現(xiàn)(low版本 ):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//創(chuàng)建一個(gè)新節(jié)點(diǎn)
struct ListNode* newNode(int x)
{
  
    struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (newnode == NULL)
	{
		printf("申請(qǐng)新的節(jié)點(diǎn)失敗:\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)//當(dāng)兩個(gè)鏈表都不為NULL時(shí)
    {
        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;
    }
    //一方已經(jīng)為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;
        }
}

優(yōu)化點(diǎn):

①:將三種情況合并處理

如果兩個(gè)鏈表只要一方有數(shù)據(jù),則表示相加還需要繼續(xù).此時(shí)為避免空指針(NULL),將短的一方設(shè)置為0再與長(zhǎng)鏈表相加.
短的一方不再繼續(xù)后移(->next),用0代替.

②最后結(jié)點(diǎn)進(jìn)位代碼可以更加簡(jiǎn)潔一些.

2.2 代碼實(shí)現(xiàn)(優(yōu)化版本):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//創(chuàng)建一個(gè)新節(jié)點(diǎn)
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;//通過這個(gè)指針遍歷sum鏈表
    int spillnum=0;//進(jìn)位數(shù)
    while(l1||l2)//當(dāng)兩個(gè)鏈表其中一個(gè)還有元素的時(shí)候
    {   
       //如果一方為空,則將其值設(shè)置為0.
        int data1= l1==NULL ? 0 : l1->val;
        int data2= l2==NULL ? 0 : l2->val;

        int sum=(data1+data2+spillnum);//兩數(shù)之和+進(jìn)位數(shù)
        struct ListNode*newnode=newNode(sum%10);

        spillnum=sum/10;//處理進(jìn)位
        //為sum鏈表新增結(jié)點(diǎn)
        sumtail->next=newnode;
        sumtail=sumtail->next;

        if(l1)//如果L1不是NULL,則后移.
        l1=l1->next;
        if(l2)//如果L2不是NULL,則后移.
        l2=l2->next;
    }
    //最后一個(gè)結(jié)點(diǎn)也可能要進(jìn)位
    if(spillnum!=0)//如果進(jìn)位數(shù)不是0,說明最后一次相加需要進(jìn)位
    {
        struct ListNode*newnode=newNode(spillnum);
        sumtail->next=newnode;
    }
     return sum->next;
}

本題的解題經(jīng)驗(yàn)就分享到這里了,下次見!

文章來源地址http://www.zghlxwxcb.cn/news/detail-409652.html

到了這里，關(guān)于力扣---兩數(shù)相加(c語言版)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！