iT邦幫忙

2023 iThome 鐵人賽

DAY 5
1

模擬加法

解題思路

兩個鏈結串列的數字是從個位開始存儲的,所以我們可以直接按位相加。

我們同時遍歷兩個鏈結串列,把每一位的數字和進位值相加,得到當前位數的和。然後,我們把和的個位數作為答案鏈結串列的一個節點,把和的十位數作為下一位的進位值。

如果兩個鏈結串列長度不一樣,我們可以把短的那個鏈結串列後面補 https://latex.codecogs.com/svg.image?0

最後,如果遍歷完還有進位值,我們要在答案鏈結串列後面加上一個節點,節點的值就是進位值。

跟一流的人才幹大事,享受成功進步的高級樂趣!
內推機會來啦!能與優秀的程式設計師共事,是特別痛快的事,因為厲害的工程師大神會刺激你想要迎頭趕上的上進心,尤其是一起討論解決方案時,他們會觸發你有更好的解決思維能力,彼此共同成長並且一起享受解謎與破關般的樂趣。 你一定聽得懂我在說甚麼感覺,趕快把握機會,動動手指投遞履歷吧! 立即加入「面試讀書會」,和大家一起準備面試!

https://ithelp.ithome.com.tw/upload/images/20230915/20151958nT7kgUzy4M.png 內推機會 https://ithelp.ithome.com.tw/upload/images/20230902/20151958hbhGNE7BJ4.png 加入讀書會 (邀請碼:2316)

程式

class Solution {
    fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
        val root = ListNode(0)
        var p1 = l1
        var p2 = l2
        var pointer = root
        var carry = 0

        while (p1 != null || p2 != null || carry > 0) {
            val num1 = p1?.`val` ?: 0
            val num2 = p2?.`val` ?: 0
            val sum = num1 + num2 + carry
            carry = sum / 10
            pointer.next = ListNode(sum % 10)
            pointer = pointer.next!!
            p1 = p1?.next
            p2 = p2?.next
        }

        return root.next
    }
}

複雜度分析

  • 時間複雜度:
    https://latex.codecogs.com/svg.image?%5Cmathcal%7BO%7D(%5Cmax%20(m%2C%20n)),其中 mn 分別代表兩個鏈結串列的長度。因為我們需要遍歷兩個鏈結串列的所有位置,而每個位置的處理時間都是常數級別的。

  • 空間複雜度:
    https://latex.codecogs.com/svg.image?O(1)。我們只需要常數級別的空間來存儲進位值和答案鏈結串列當前的節點。要注意的是,因為鏈結串列作為回傳值,所以不會計入空間複雜度。

pp 更多 LeetCode 解答在此,一起來學習!

內推機會來啦!

跟一流的人才幹大事,享受成功進步的高級樂趣!

https://ithelp.ithome.com.tw/upload/images/20230915/20151958nT7kgUzy4M.png 內推機會 https://ithelp.ithome.com.tw/upload/images/20230902/20151958hbhGNE7BJ4.png 加入讀書會 (邀請碼:2316)

上一篇
LeetCode 232. Implement Queue using Stacks
下一篇
LeetCode 1971. Find if Path Exists in Graph
系列文
破解 Android 工程師面試白板題:30 道面試題目與解答30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言