2022/04/01

Leetcode Note: Go - Merge Two Sorted Lists

Merge Two Sorted Lists - LeetCode
https://leetcode.com/problems/merge-two-sorted-lists/

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

所感

  • 愚直に実装するなら 2つ のリストをマージしてから改めてソートすれば良さそう
    • わざわざソート済みのリストが用意されているので、もっとよいソート方法がありそうだが

実装準備

type ListNode struct {
    Val int
    Next *ListNode
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    return &ListNode{}
}


func main() {
    list1 := ListNode{
        Val: 0,
    }
    list2 := ListNode{
        Val: 0,
    }
    fmt.Println(list1, list2)
    
    p := mergeTwoLists(&list1, &list2)
    fmt.Println(p)
}
  • そもそも実装準備でミニマムな環境をどう実装していいかも分からず・・・
  • ListNode に含まれる Next は、どう表現したら良いんだろう
  • mergeTwoLists が main からどう呼ばれているのかイメージできず

回答

Golang Solution - LeetCode Discuss
https://leetcode.com/problems/merge-two-sorted-lists/discuss/1890300/Golang-Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    var head ListNode
    current := &head
    
    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            current.Next = list1
            list1 = list1.Next
        } else {
            current.Next = list2
            list2 = list2.Next
        }
		// advance to next value
        current = current.Next
    }
    
    if list1 != nil {
        current.Next =  list1
    } else {
        current.Next =  list2
    }
    return head.Next
}
  • current の ListNode を定義
  • list1 と list2 として nil が設定されていないことをチェックしつつ、ループ
    • ソート処理
      • list1.Val と list2.Val を比較して、小さい値を current.Next にする
      • current.Next を設定した list を次のステップにすすめるため list.Next を更新
    • ループをすすめるため current.Next を更新
  • list1 が nil じゃなければ、ループのため current.Next を list1 にする
  • list1 が nil なら、ループのため current.Next を list2 にする
  • head.Next (== &current.Next) を return

たぶん再帰的な呼び出され方を想定している関数なので、その辺のイメージができていない課題感あり

See Also