Leetcode Note: Go - Add Two Numbers

Add Two Numbers - LeetCode
https://leetcode.com/problems/add-two-numbers/

• Go 言語で取り組んだメモ

所感

• LeetCode を本格的に初めてから初の休日なので、難易度 Medium に挑戦

• やることとしては

  • 与えられる 2つ の linked list を逆順にソート
  • 逆順にしたソートした linked list を合算

  • 合算結果を逆順にして linked list として return する

    /**
    * Definition for singly-linked list.
    * type ListNode struct {
    *     Val int
    *     Next *ListNode
    * }
    */
    
    func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // TODO:
    }

• linked list の概念は何となく理解しているつもりだが、この linked list をどう呼び出しているのかイメージできず…

  • そもそも golang で最小限の linked list を実装して動かすというアクションが必要そう

• あと input が 9,9,9,9,9,9,9 と 9,9,9,9 の場合に output が 8,9,9,9,0,0,0,1 になるロジックが理解できていない

  • 9,9,9,9,9,9,9 + 0,0,0,9,9,9,9 = 1,0,0,0,9,9,9,8 => これを逆順にして 8,9,9,9,0,0,0,1 か

回答

[GO] Best run was 3 ms, faster than 98.82% - LeetCode Discuss
https://leetcode.com/problems/add-two-numbers/discuss/1868937/GO-Best-run-was-3-ms-faster-than-98.82

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil || l2 == nil {
        return nil
    }
    
    result := new(ListNode)
    cur := result
    
    for ; l1 != nil || l2 != nil; {
        var placeSum int
        switch {
            case l1 == nil:
                placeSum = cur.Val + l2.Val
            
            case l2 == nil:
                placeSum = cur.Val + l1.Val
                
            default:
                placeSum = cur.Val + l1.Val + l2.Val
        }
        
        if placeSum < 10 {
            cur.Val = placeSum
            if (l1 != nil && l1.Next != nil) || (l2 != nil && l2.Next != nil) {
                cur.Next = new(ListNode)
                cur = cur.Next
            }

        } else {
            cur.Val = placeSum % 10
            cur.Next = new(ListNode)
            cur.Next.Val = 1
            cur = cur.Next
        }
        
        if l1 != nil {
            l1 = l1.Next
        }
            
        if l2 != nil {
            l2 = l2.Next
        }
    }
    
    return result
}

• 引数で受けた 2つ の linked list の nil チェック
• 関数の処理で使用する、新しい ListNode を定義して cur に代入
• l1 または l2 が nil で無い間ループ
  • 合算した結果は placeSum で扱う
  • switch => 合算処理
    • l1 が nil なら cur.Val と l2.Val を合算
    • l2 が nil なら cur.Val と l1.Val を合算
    • それ以外なら cur.Val と l1.Val と 2.Val を合算
  • if => 合算結果 placeSum に応じて処理
    • 合算結果が 10 以下であれば、ループ処理の準備
      • l1, l2 それぞれの nil と Next が nil かをチェック
      • Next が nil じゃなければ cur.Next として新しい ListNode を定義して cur = cur.Next
    • 合算結果が 10 以上であれば、桁の繰り上げ処理
      • cur.Val は合算した下一桁の数字を維持
      • cur.Next として新しい ListNode を定義
      • cur.Next.Val を 1 に設定しておく
  • if => ループ処理
    • l1, l2 の nil チェックを行い、 nil じゃなければ Next へ