最近、LeetCode の問題を解きはじめた。
LeetCode とは、プログラミングの問題を集めた学習サイト。企業のコーディング試験に利用されることもあるらしい。
簡単な問題を数問しか解いていないが、頭の体操のような感じでたのしい。

その中で、Merge Two Sorted Lists という問題があった。
自分は、この問題を逐次処理的な方法で解いていたが、他の人が再帰でシンプルなコードで解いているのを見つけた。
再帰での解法が理解しづらかったため、理解のためにブログに書くことにした。

Merge Two Sorted Lists の問題
- 出題内容
- 再帰を用いたコード
  - merge_two_lists メソッドがしていること
  - 処理を追う
感想

Merge Two Sorted Lists の問題

問題はこちら。
https://leetcode.com/problems/merge-two-sorted-lists/

出題内容

2つのソート済み連結リスト list1 と list2 の先頭が与えられる
この2つのリストを1つのソート済みリストに結合する
- このリストは、最初の2つのリストのノードをつなぎ合わせたものでなければならない
マージされた連結リストの先頭を返す

インターフェースはこのように出題されている。

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} list1
# @param {ListNode} list2
# @return {ListNode}
def merge_two_lists(list1, list2)
    
end

連結リストとは、値と、次のデータへの参照がセットになっているデータ構造のこと。
ListNode クラスは、@val に値、@next に次の ListNode を保持する構造になっている。

例えば、以下の ListNode が与えられた場合。

list1 = [1,2,4]
list2 = [1,3,4]

list1 と list2 を inspect で確認すると、@next に次の ListNode が保持されている。
@next が nil の ListNode は、リストの最後である。

#<ListNode:0x00007f2a933fa768 @val=1, 
  @next=#<ListNode:0x00007f2a933fa560 @val=2, 
    @next=#<ListNode:0x00007f2a933f99a8 @val=4, 
      @next=nil>>>

#<ListNode:0x00007f2a933f94d0 @val=1, 
  @next=#<ListNode:0x00007f2a933f9430 @val=3, 
    @next=#<ListNode:0x00007f2a933f93b8 @val=4, 
      @next=nil>>>

再帰を用いたコード

以下のように、再帰を用いたコードを書いている方がいた。
このページを参照させていただいた。

def merge_two_lists(list1, list2)
  return list1 if list2.nil?
  return list2 if list1.nil?

  if list1.val < list2.val
    list1.next = merge_two_lists(list1.next, list2)
    list1
  else
    list2.next = merge_two_lists(list1, list2.next)
    list2
  end
end

merge_two_lists メソッドがしていること

merge_two_lists メソッドの中で、自分自身を呼び出している（再帰）
merge_two_lists メソッドがやりたいことは以下である。
1. リスト1 とリスト2の値を先頭のノードから比較し、値が小さいリストを特定し、その次のノードを決める 。
2. 1 の処理を、2つのリストの終端まで行って、値が小さい順から連結していく。
3. 最終的に、連結したリストの先頭を返す 。

処理を追う

以下の例で考える。

list1 = [1, 5]
list2 = [3, 4]

このようなデータ構造になっている。

list1: 
#<ListNode:0x00007f0780821778 @val=1, 
  @next=#<ListNode:0x00007f0780821570 @val=5, 
    @next=nil>>

list2: 
#<ListNode:0x00007f0780820b20 @val=3, 
  @next=#<ListNode:0x00007f0780820a80 @val=4, 
    @next=nil>>

1周目の呼出し

list1, list2 はどちらも nil ではない（つまり、リストの終端ではない）
list1.val = 1, list2.val = 3
list1.val < list2.val の条件に合致
- list1 の値が小さいと判定されたため、list1 の次に参照すべき（＝小さい）ノードを見つけるために merge_two_listsメソッドを list1の次のノードとlist2を引数にして呼び出している
- list1.next に merge_two_lists(list1.next, list2) を設定する
  - 2周目の呼出しへ

2周目の呼出し

list1: 
#<ListNode:0x00007f0780821570 @val=5, 
  @next=nil>

list2
#<ListNode:0x00007f0780820b20 @val=3, 
  @next=#<ListNode:0x00007f0780820a80 @val=4, 
  @next=nil>>

list1, list2 はどちらも nil ではない（つまり、リストの終端ではない）
list1.val = 5, list2.val = 3
else（list.1val >= list2.val ）に入る
- list2 の値（3）が小さいと判定されたため、list2 の次に参照すべき（＝小さい）ノードを見つけるために merge_two_listsメソッドを list1 と list2 の次のノードを引数にして呼び出している
- list2.next に merge_two_lists(list1, list2.next) を設定する
  - 3周目の呼出しへ

3周目の呼出し

list1
#<ListNode:0x00007f0780821570 @val=5, @next=nil>

list2
#<ListNode:0x00007f0780820a80 @val=4, @next=nil>

list1, list2 はどちらも nil ではない（つまり、リストの終端ではない）
list1.val = 5, list2.val = 4
else（list.1val >= list2.val ）に入る
- list2 の値（4）が小さいと判定されたため、list2 の次に参照すべき（＝小さい）ノードを見つけるために merge_two_listsメソッドを list1 と list2 の次のノードを引数にして呼び出している
- list2.next に merge_two_lists(list1, list2.next) を設定する
  - 4周目の呼出しへ

4周目の呼出し

list1
#<ListNode:0x00007f0780821570 @val=5, @next=nil>

list2:
nil

list2 が nil （リストの終端）のため、 list1（list1.val = 5）が返される
- list2.val = 4 の次の要素として設定される

3周目の merge_two_lists メソッド呼出し後の処理で、list2（ list2.val = 4 ）が返される
- list2.val = 3 の次の要素として設定される

2周目の merge_two_lists メソッド呼出し後の処理で、list2（ list2.val = 3 ）が返される
- list1.val = 1 の次の要素として設定される

1周目の merge_two_lists メソッド呼出し後の処理で、list1（ list1.val = 1 ）が返される
最終的に、一番値が小さい先頭のノードである list1 が返される

感想

当初、自分は iterative なやり方で ListNode を each で生成するような処理を書いていた。
Accepted となったが、メモリ効率が良くなく、コードがごちゃついて今一歩だった。

# 今一歩なコード・・・
def merge_two_lists(list1, list2)
  sorted_array = (get_list_vals(list1) + get_list_vals(list2)).sort { |a, b| b <=> a }

  generate_list(sorted_array)
end

def get_list_vals(list)
  result = []
  
  while !list.nil?
    result << list.val
    list = list.next
  end

  result
end

def generate_list(array)
  # arrayの最初の1文字を取り出してListNodeの最後の要素を作成する
  node = ListNode.new(array.shift, nil)
  array.each { |num| node = ListNode.new(num, node) }
  node
end

他の方の解答をみていると、再帰のアプローチがあったので、理解したいと考えこの記事を書いた。
書いてあることの理解は進んだが、再帰のロジックを自分で考えて書くことは難しいと感じた。
再帰でロジックを考えるには、その関数がどのような繰り返し処理を行うか考えることと、終了条件を考える（自分自身を呼び出すため、どこかで終了しないと無限に続いてしまう）ことがポイントのように感じた。

再帰は理解が難しいけれど、再帰を使って解けるとエレガントだと思う。
自分で再帰でロジックを考えて書けるようになりたい。

日々のこと

まいにちの暮らしをつれづれ書きます

LeetCode / Merge Two Sorted Lists の再帰のコードを理解する