LeetCode高頻算法面試題 - 002 - 兩數(shù)相加

題目來源于 LeetCode 上第 2 號(hào)問題:兩數(shù)相加李丰。題目難度為 Medium圃阳,目前通過率為 33.9% 。

題目描述

給出兩個(gè) 非空 的鏈表用來表示兩個(gè)非負(fù)的整數(shù)罢荡。其中憨募,它們各自的位數(shù)是按照 逆序 的方式存儲(chǔ)的紧索,并且它們的每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字。

如果菜谣,我們將這兩個(gè)數(shù)相加起來珠漂,則會(huì)返回一個(gè)新的鏈表來表示它們的和。

您可以假設(shè)除了數(shù)字 0 之外尾膊,這兩個(gè)數(shù)都不會(huì)以 0 開頭媳危。

<font color=#FF000 >題目難度: ★★, 中等</font>


image.png

示例 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]

提示:

每個(gè)鏈表中的節(jié)點(diǎn)數(shù)在范圍 [1, 100] 內(nèi)
0 <= Node.val <= 9
題目數(shù)據(jù)保證列表表示的數(shù)字不含前導(dǎo)零

題目解析

設(shè)立一個(gè)表示進(jìn)位的變量carried,建立一個(gè)新鏈表冈敛,把輸入的兩個(gè)鏈表從頭往后同時(shí)處理待笑,每兩個(gè)相加,將結(jié)果加上carried后的值作為一個(gè)新節(jié)點(diǎn)到新鏈表后面抓谴。

代碼實(shí)現(xiàn)

tips: 以下代碼是使用Go代碼實(shí)現(xiàn)的不同解法, 文章最后可以看C++暮蹂、C寞缝、Java、Python實(shí)現(xiàn)

1仰泻、循環(huán)遍歷, 進(jìn)行求和

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    var carry int
    resultList := &ListNode{}
    current := resultList

    for{
        if l1 == nil && l2 == nil && carry == 0{
            break
        }

        if l1 != nil{
            carry += (*l1).Val
            l1 = l1.Next
        }

        if l2 != nil{
            carry += (*l2).Val
            l2 = l2.Next
        }

        node := ListNode{}

        if carry <= 9{
            node = ListNode{
                Val: carry,
            }
            carry = 0
        }else{
            node = ListNode{
                Val: carry - 10,
            }
            carry = 1
        }

        current.Next = &node
        current = &node
    }

    return resultList.Next
}

執(zhí)行結(jié)果


image.png

2荆陆、改進(jìn)方法, <font color=#FF000 >如果l1、l2長度差別很大, 就可以直接利用偏長鏈表后面的部分, 避免重復(fù)new Node節(jié)點(diǎn)</font>集侯。

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    var carry int
    resultList := &ListNode{}
    current := resultList

    for{
        node := ListNode{}
        if l1 == nil && l2 == nil && carry == 0{
            break
        }

        if l1 != nil{
            if l2 == nil && carry == 0{
                current.Next = l1
                break
            }else{
                carry += (*l1).Val
                l1 = l1.Next
            }
        }

        if l2 != nil{
            if l1 == nil && carry == 0{
                current.Next = l2
                break
            }else{
                carry += (*l2).Val
                l2 = l2.Next
            }
        }

        if carry <= 9{
            node = ListNode{
                Val: carry,
            }
            carry = 0
        }else{
            node = ListNode{
                Val: carry - 10,
            }
            carry = 1
        }

        current.Next = &node
        current = &node
    }

    return resultList.Next
}

執(zhí)行結(jié)果


image.png

3被啼、方法三利用遞歸方法對(duì)兩個(gè)array進(jìn)行求和, 這里就不展開細(xì)講了

其他語言版本

C++

/// 時(shí)間復(fù)雜度: O(n)
/// 空間復(fù)雜度: O(n)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

        ListNode *p1 = l1, *p2 = l2;
        ListNode *dummyHead = new ListNode(-1);
        ListNode* cur = dummyHead;
        int carried = 0;
        while(p1 || p2 ){
            int a = p1 ? p1->val : 0;
            int b = p2 ? p2->val : 0;
            cur->next = new ListNode((a + b + carried) % 10);
            carried = (a + b + carried) / 10;

            cur = cur->next;
            p1 = p1 ? p1->next : NULL;
            p2 = p2 ? p2->next : NULL;
        }

        cur->next = carried ? new ListNode(1) : NULL;
        ListNode* ret = dummyHead->next;
        delete dummyHead;
        return ret;
    }
};

執(zhí)行結(jié)果

image.png

Java

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        int carry = 0;

        while(l1 != null || l2 != null)
        {
            int sum = carry;
            if(l1 != null)
            {
                sum += l1.val;
                l1 = l1.next;
            }
            if(l2 != null)
            {
                sum += l2.val;
                l2 = l2.next;
            }
            // 創(chuàng)建新節(jié)點(diǎn)
            carry = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
    
        }
        if (carry > 0) {
            cur.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}

執(zhí)行結(jié)果

image.png

Python

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        res=ListNode(0)
        head=res
        carry=0
        while l1 or l2 or carry!=0:
            sum=carry
            if l1:
                sum+=l1.val
                l1=l1.next
            if l2:
                sum+=l2.val
                l2=l2.next
            # set value
            if sum<=9:
                res.val=sum
                carry=0
            else:
                res.val=sum%10
                carry=sum//10
            # creat new node
            if l1 or l2 or carry!=0:
                res.next=ListNode(0)
                res=res.next
        return head

執(zhí)行結(jié)果

image.png

幾種語言運(yùn)行效果對(duì)比

image.png
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市棠枉,隨后出現(xiàn)的幾起案子浓体,更是在濱河造成了極大的恐慌,老刑警劉巖辈讶,帶你破解...
    沈念sama閱讀 212,080評(píng)論 6 493
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件命浴,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡荞估,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,422評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門稚新,熙熙樓的掌柜王于貴愁眉苦臉地迎上來勘伺,“玉大人,你說我怎么就攤上這事褂删》勺恚” “怎么了?”我有些...
    開封第一講書人閱讀 157,630評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵屯阀,是天一觀的道長缅帘。 經(jīng)常有香客問我,道長难衰,這世上最難降的妖魔是什么钦无? 我笑而不...
    開封第一講書人閱讀 56,554評(píng)論 1 284
  • 正文 為了忘掉前任,我火速辦了婚禮盖袭,結(jié)果婚禮上失暂,老公的妹妹穿的比我還像新娘。我一直安慰自己鳄虱,他們只是感情好弟塞,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,662評(píng)論 6 386
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著拙已,像睡著了一般决记。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上倍踪,一...
    開封第一講書人閱讀 49,856評(píng)論 1 290
  • 那天系宫,我揣著相機(jī)與錄音索昂,去河邊找鬼。 笑死笙瑟,一個(gè)胖子當(dāng)著我的面吹牛楼镐,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播往枷,決...
    沈念sama閱讀 39,014評(píng)論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼框产,長吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來了错洁?” 一聲冷哼從身側(cè)響起秉宿,我...
    開封第一講書人閱讀 37,752評(píng)論 0 268
  • 序言:老撾萬榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎屯碴,沒想到半個(gè)月后描睦,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,212評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡导而,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,541評(píng)論 2 327
  • 正文 我和宋清朗相戀三年忱叭,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片今艺。...
    茶點(diǎn)故事閱讀 38,687評(píng)論 1 341
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡韵丑,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出虚缎,到底是詐尸還是另有隱情撵彻,我是刑警寧澤,帶...
    沈念sama閱讀 34,347評(píng)論 4 331
  • 正文 年R本政府宣布实牡,位于F島的核電站陌僵,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏创坞。R本人自食惡果不足惜碗短,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,973評(píng)論 3 315
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望题涨。 院中可真熱鬧豪椿,春花似錦、人聲如沸携栋。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,777評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽婉支。三九已至鸯隅,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背蝌以。 一陣腳步聲響...
    開封第一講書人閱讀 32,006評(píng)論 1 266
  • 我被黑心中介騙來泰國打工炕舵, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人跟畅。 一個(gè)月前我還...
    沈念sama閱讀 46,406評(píng)論 2 360
  • 正文 我出身青樓咽筋,卻偏偏與公主長得像,于是被迫代替她去往敵國和親徊件。 傳聞我的和親對(duì)象是個(gè)殘疾皇子奸攻,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,576評(píng)論 2 349