0002.Add Two Numbers

題目

題目大意

解題思路

鏈表雙指標技巧 和加法運算過程中對進位的處理。 注意這個 carry 變數的處理，在我們手動類比加法過程的時候會經常用到。

• 遍歷 l1跟 l2. 講兩個list的val相加, 並且記錄進位的值給next使用
• 最後如果 carry 還有的話, 需要產生一個新的節點

Big O

• 時間複雜 : O(max⁡(m,n) 時間複雜度： O(max⁡(m,n)) ，其中 m 和 n 分別為兩個鏈表的長度。 我們要遍歷兩個鏈表的全部位置，而處理每個位置只需要 O(1) 的時間

• 空間複雜 : O(1) O(1) 。 注意返回值不計入空間複雜度

來源

• https://leetcode.com/problems/add-two-numbers/description/
• https://leetcode.cn/problems/

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0002.Add-Two-Numbers/main.go

package addtwonumbers

// 時間複雜 O(max(m,n)), 空間複雜 O(1)
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// 遍歷 l1跟 l2. 講兩個list的val相加, 並且記錄進位的值給next使用
// 最後如果 carry 還有的話, 需要產生一個新的節點
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    var result, tail *ListNode
    carry := 0
    for l1 != nil || l2 != nil {
        n1, n2 := 0, 0
        if l1 != nil {
            n1 = l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            n2 = l2.Val
            l2 = l2.Next
        }
        sum := n1 + n2 + carry
        sum, carry = sum%10, sum/10

        if result == nil {
            result = &ListNode{Val: sum, Next: nil}
            tail = result
        } else {
            tail.Next = &ListNode{Val: sum, Next: nil}
            tail = tail.Next
        }
    }
    // 最後如果 carry 還有的話, 需要產生一個新的節點
    if carry > 0 {
        tail.Next = &ListNode{Val: carry, Next: nil}
    }
    return result
}

Benchmark