兩數相加

aside section._1OhGeD · · 105 次點擊 · · 開始瀏覽    

兩數相加

題目

來自: https://leetcode-cn.com/problems/add-two-numbers/

給出兩個 非空 的鏈表用來表示兩個非負的整數。其中,它們各自的位數是按照逆序的方式存儲的,并且它們的每個節點只能存儲一位數字。

如果,我們將這兩個數相加起來,則會返回一個新的鏈表來表示它們的和。

您可以假設除了數字 0 之外,這兩個數都不會以 0 開頭。

示例:

輸入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出:7 -> 0 -> 8
原因:342 + 465 = 807

Go編程實現

思路:迭代計算每位數字的和,記錄進位。當全部數位和進位計算完畢,結果得到。

代碼如下:

// 單向鏈表結構
type ListNode struct {
    Val  int
    Next *ListNode
}

func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    //判斷是否存在操作數為 0 的特例
    if l1.Val == 0 && l1.Next == nil {
        return l2
    }
    if l2.Val == 0 && l2.Next == nil {
        return l1
    }

    result := &ListNode{}
    //迭代處理的結果節點,從第一個開始
    node := result
    // 進位
    var carry int
    // 和
    v := 0
    for {
        // 若 l1 還有,則累加,同時切換下一個l1
        if l1 != nil {
            v += l1.Val
            l1 = l1.Next
        }
        // 若 l2 還有,則累加,同時切換下一個 l2
        if l2 != nil {
            v += l2.Val
            l2 = l2.Next
        }
        //累加進位
        v += carry
        carry = v / 10 // 進位
        node.Val = v % 10 // 當前位
        // 若 l1 l2 進位都沒了,結束
        if l1 == nil && l2 == nil && carry == 0 {
            break
        }
        // 構建下一個結果節點
        node.Next = &ListNode{}
        node = node.Next
        v = 0
    }

    return result
}

本實現在 LeetCode 上測試通過,結果為:

執行用時 : 8 ms , 在所有 golang 提交中擊敗了 96.84% 的用戶。

內存消耗 : 4.9 MB , 在所有 golang 提交中擊敗了 94.01% 的用戶。

歡迎關注 紅牛慕課


subscribe_gin.png

本文來自:簡書

感謝作者:aside section._1OhGeD

查看原文:兩數相加

入群交流(和以上內容無關):Go中文網 QQ 交流群:729884609 或加微信入微信群:274768166 備注:入群;關注公眾號:Go語言中文網

105 次點擊  
加入收藏 微博
暫無回復
添加一條新回復 (您需要 登錄 后才能回復 沒有賬號 ?)
  • 請盡量讓自己的回復能夠對別人有幫助
  • 支持 Markdown 格式, **粗體**、~~刪除線~~、`單行代碼`
  • 支持 @ 本站用戶;支持表情(輸入 : 提示),見 Emoji cheat sheet
  • 圖片支持拖拽、截圖粘貼等方式上傳