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 に設定しておく
- 合算結果が 10 以下であれば、ループ処理の準備
- if => ループ処理
- l1, l2 の nil チェックを行い、 nil じゃなければ Next へ