LeetCodeの入出力値の型に騙されるな - 206. Reverse Linked List

# はじめに

LeetCodeは基本的に良問揃いだと思いますが、その問題説明文は意外と雑に感じる時があります。Atcoder[^1] からスタートして、LeetCodeに移り、鼻歌まじりで楽しく1日1LC[^2] していたのですが、進めるにつれ、ちょいちょい雑な問題文に出会ってリズムが崩れたので、その対策をメモしておこうと思います。言語はRubyでやってます。

[206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/) の Ruby の解を知りたいだけの場合は、最後の方の「参考になったサイト」を見るのが早いと思います。

# 前兆

[14. Longest Common Prefix](https://leetcode.com/problems/longest-common-prefix/) あたりで、回答欄に見慣れないコメント文を見つける。

```ruby
# @param {String[]} strs
# @return {String}
def longest_common_prefix(strs)
end
```

[StackOverflow 先生に聞いてみると](https://stackoverflow.com/questions/55895585/what-does-param-and-return-mean-in-ruby/55895662)、この2行は [`YARD`というドキュメント生成ツール](https://yardoc.org/)のお作法で書かれているようだ。

その意味は `longest_common_prefix` は `strs`という`{String[]}`インスタンスを引数にとり、`{String}`インスタンスを返すということのようだ

ところで、`{String[]}`インスタンスってなに？ 問題文には

```ruby

Input:["flower","flow","flight"]
```

ってなってるので、入力は `Array` っぽく思えるけど、これ実は文字列なの？ということは、配列にしたかったら、`eval(strs)`とかした方がいいの？

確かめてみると

```ruby
# @param {String[]} strs
# @return {String}
def longest_common_prefix(strs)
  p strs.class # => Array
end
```
普通に `Array` でした... `{String[]}`ってなに？、Stringの配列ってこと？Java 族の人が書いた？

# 206. Reverse Linked List

[Linked Listを反転させる問題](https://leetcode.com/problems/reverse-linked-list/) なのだがこれも、問題文だけ見ると「え？」となる。

```
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
```
とかなっていて、いやいや、これが本当の入出力なら、趣旨を無視する輩なら、普通に文字列処理で返せてしまうがな。たとえばこんなワンライナーで。

```ruby

def reverse_list(head)
  split("->").slice(0, head.split("->").size-1).reverse.push("NULL").join("->")
end
```

しかも、`Run Code` でテストしてみるとそこの表記は

```ruby

Your input: [1,2,3,4,5]
Your output: [1,2,3,4,5]
Expected: [5,4,3,2,1]
```

とかでてくるので、「え？input, outputともに配列？」ってなる。が、もちろんちがう。回答欄をみてみると：

```ruby

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val)
#         @val = val
#         @next = nil
#     end
# end

# @param {ListNode} head
# @return {ListNode}
def reverse_list(head)
end
```

`YARD` 的には `ListNode`インスタンスを受け取って、`ListNode`インスタンスを返せということらしい。どんな入力値渡してきているのかを確認するために、`Run Code` で入力値をそのまま直接標準出力に出してみる。

```ruby

# @param {ListNode} head
# @return {ListNode}
def reverse_list(head)
  p head # => #<ListNode:0x0000000001a4ea38 @val=1, @next=#<ListNode:0x0000000001a4ea10 @val=2, @next=#<ListNode:0x0000000001a4e9e8 @val=3, @next=#<ListNode:0x0000000001a4e9c0 @val=4, @next=#<ListNode:0x0000000001a4e998 @val=5, @next=nil>>>>>
end
```

なるほど、確かに `ListNode`オブジェクトっぽいものが渡されている。わかってきた。ということはおそらく、この入力値はこのように作られているのではないか

```ruby

class ListNode
  attr_accessor :val, :next
  def initialize(val)
    @val = val
    @next = nil
  end
end

ln1 = ListNode.new(1)
ln2 = ListNode.new(2)
ln3 = ListNode.new(3)
ln4 = ListNode.new(4)
ln5 = ListNode.new(5)

ln1.next = ln2
ln2.next = ln3
ln3.next = ln4
ln4.next = ln5

p ln1 # => #<ListNode:0x007fbd46967138 @val=1, @next=#<ListNode:0x007fbd469670c0 @val=2, @next=#<ListNode:0x007fbd46967048 @val=3, @next=#<ListNode:0x007fbd46967020 @val=4, @next=#<ListNode:0x007fbd46966ff8 @val=5, @next=nil>>>>>
```

さっき、`p head` したときと同じような出力になっていて、それっぽい感じです。ここで意味がわかってきたので、タイトルの趣旨としては終わりですが、ついでに206の解法について考えてみます。

# Solution

基本的に、ポインタを反転させるという考え方のようです。

## Iterative

繰り返し的な解き方

```ruby

def reverse_list(head)
  prev = nil
  curr = head
  #puts "curr: #{curr}, prev: #{prev}"
  until curr.nil?
    temp = curr.next
    curr.next = prev
    prev = curr
    curr = temp
    #puts "curr: #{curr}, prev: #{prev}, temp: #{temp}"
  end
  prev
end
```

要は、最後の `nil` に当たるまでノード毎にポインタを反転させていくみたいです。絵で書くとこんな感じでしょうか。

```ruby

prev
↓
nil  1 -> 2 -> 3 -> 4 -> 5 -> nil
     ↑
     curr

curr = head(=1)
temp <= curr.next(=2)
curr.next <= prev(=nil)
prev <= curr(=1)
curr <= temp(=2)

       prev
       ↓
nil <- 1    2 -> 3 -> 4 -> 5 -> nil
            ↑
            curr

curr = 2
temp <= curr.next(=3)
curr.next <= prev(=1)
prev <= curr(=2)
curr <= temp(=3)

            prev
            ↓
nil <- 1 <- 2    3 -> 4 -> 5 -> nil
                 ↑
                 curr
curr = 3
temp <= curr.next(=4)
curr.next <= prev(=2)
prev <= curr(=3)
curr <= temp(=4)

                 prev
                 ↓
nil <- 1 <- 2 <- 3    4 -> 5 -> nil
                      ↑
                      curr
                    
curr = 4
temp <= curr.next(=5)
curr.next <= prev(=3)
prev <= curr(=4)
curr <= temp(=5)

                      prev
                      ↓
nil <- 1 <- 2 <- 3 <- 4    5 -> nil
                           ↑
                           curr
curr = 5
temp <= curr.next(=nil)
curr.next <= prev(=4)
prev <= curr(=5)
curr <= temp(=nil)

                           prev
                           ↓
nil <- 1 <- 2 <- 3 <- 4 <- 5    nil
                                ↑
                                curr
curr = nil になったので終わり
```

## Recursive

再起的な解き方

```ruby

def reverse_list(head)
  return head if head.nil? || head.next.nil?

  p = reverse_list(head.next)
  head.next.next = head
  head.next = nil
  p
end
```

分かりやすくはないですね。`head.next.next = head` とか何やってんの？なんですが、たとえば、`2`からみて、`3`のノード（つまり`head.next`）のポインタ（つまり`head.next.next`）を自分に向けるみたいな感じでしょうか

```
1 -> 2 -> 3 -> 4 -> 5 -> nil
     ↑
    ココ
```


## パフォーマンス

#### Iterative
```yaml

Runtime: 36 ms, faster than 72.64% of Ruby online submissions for Reverse Linked List.
Memory Usage: 9.5 MB, less than 100.00% of Ruby online submissions for Reverse Linked List.
```

#### Recursive
```yaml

Runtime: 32 ms, faster than 93.01% of Ruby online submissions for Reverse Linked List.
Memory Usage: 9.9 MB, less than 100.00% of Ruby online submissions for Reverse Linked List.
```


# 参考にしたサイト

[LeetCode in Ruby: 206 Reverse Linked List](https://dev.to/algobot76/leetcode-in-ruby-206-reverse-linked-list-3gi9)[^3]

[^1]: Atcoderは確か基本的に入力値を標準入力からテキストで受けとる形だったと思いますので、型の話は無縁だと思います。
[^2]: 一日に一つLeetCodeの問題をときます
[^3]: 参考にしたというか、まんま答えです。今回の内容はここに至るまでが趣旨ですので...