はじめに
LeetCodeは基本的に良問揃いだと思いますが、その問題説明文は意外と雑に感じる時があります。Atcoder1 からスタートして、LeetCodeに移り、鼻歌まじりで楽しく1日1LC2 していたのですが、進めるにつれ、ちょいちょい雑な問題文に出会ってリズムが崩れたので、その対策をメモしておこうと思います。言語はRubyでやってます。
206. Reverse Linked List の Ruby の解を知りたいだけの場合は、最後の方の「参考になったサイト」を見るのが早いと思います。
前兆
14. Longest Common Prefix あたりで、回答欄に見慣れないコメント文を見つける。
# @param {String[]} strs
# @return {String}
def longest_common_prefix(strs)
end
StackOverflow 先生に聞いてみると、この2行は YARDというドキュメント生成ツールのお作法で書かれているようだ。
その意味は longest_common_prefix は strsという{String[]}インスタンスを引数にとり、{String}インスタンスを返すということのようだ
ところで、{String[]}インスタンスってなに？ 問題文には
Input:["flower","flow","flight"]
ってなってるので、入力は Array っぽく思えるけど、これ実は文字列なの？ということは、配列にしたかったら、eval(strs)とかした方がいいの？
確かめてみると
# @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を反転させる問題 なのだがこれも、問題文だけ見ると「え？」となる。
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
とかなっていて、いやいや、これが本当の入出力なら、趣旨を無視する輩なら、普通に文字列処理で返せてしまうがな。たとえばこんなワンライナーで。
def reverse_list(head)
split("->").slice(0, head.split("->").size-1).reverse.push("NULL").join("->")
end
しかも、Run Code でテストしてみるとそこの表記は
Your input: [1,2,3,4,5]
Your output: [1,2,3,4,5]
Expected: [5,4,3,2,1]
とかでてくるので、「え？input, outputともに配列？」ってなる。が、もちろんちがう。回答欄をみてみると：
# 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 で入力値をそのまま直接標準出力に出してみる。
# @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オブジェクトっぽいものが渡されている。わかってきた。ということはおそらく、この入力値はこのように作られているのではないか
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
繰り返し的な解き方
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 に当たるまでノード毎にポインタを反転させていくみたいです。絵で書くとこんな感じでしょうか。
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
再起的な解き方
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
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
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 List3