前往
大廳
主題

LeetCode - 445. Add Two Numbers II 解題心得

Not In My Back Yard | 2022-12-02 12:00:10 | 巴幣 0 | 人氣 210

題目連結:


題目意譯:
你被給定兩個非空連結串列(Linked List)代表著兩個非負整數。越高位的位數越早出現於串列中,且每個節點包含一個位數。將兩數相加並總和回傳成一個連結串列。

你可以假設兩個數字不包含任何前導零,除了數字 0 本身。

限制:
每個連結串列的節點數位於範圍 [1, 100] 中。
0 ≦ Node.val ≦ 9
保證串列所代表著數字不包含任何前導零。

進階:你可以在不把串列反轉的情況下解出本題嗎?



範例測資:
範例 1:
輸入: l1 = [7,2,4,3], l2 = [5,6,4]
輸出: [7,8,0,7]

範例 2:
輸入: l1 = [2,4,3], l2 = [5,6,4]
輸出: [8,0,7]

範例 3:
輸入: l1 = [0], l2 = [0]
輸出: [0]


解題思維:
前言:我沒有做進階的部分,因為我覺得這次的「進階」毫無意義可言。因為我們只要不用去動串列本身就好了,將兩個串列複製一份到兩個新的陣列或是使用兩個堆疊都可以繞過這個標準。另外,雖然還有一種不使用額外陣列或堆疊存在,但是它並非線性時間的作法,因此不在此贅述。

回歸正題,將給定的兩個串列 l1 和 l2 按照這題的作法反轉之後,再按照這題相加。最後再將結果反轉回去即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作