方針
自分で1回はプロセスを考える。解けなくてもOK。
解けなかったときは、振り返ることが可能な程度まで言語化する。
※考え方おかしくない?というのがあればご指摘くださいまし。
※解けなかった、苦戦したものを記事にする。
問題紹介
問題は以下URL参照
最初の考え
- こんなのリスト内をループさせる。配列に保存。次回ループ時に値が存在するかを判定すればいいんじゃね。
初回.py
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
mem = []
while head != None:
count = mem.count(head.val)
mem.append(head.val)
head = head.next
if count > 0:
return True
return False
思考中
- 重複してるときのテストケースで落ちた...
- link先の値が複数あるときは弾かないといけないのか...(´・ω・`)
- input中の重複数値を洗い出すとかやれば大丈夫なんだけど、制限されてて確認できない(詰んだ)
結果
Solutionsを確認しました(´・ω・`)
- 2つの速度でポインタを循環させて、一致した場合には循環しているのでTrue(ポインタの遭遇率が最近高い)
- この手の問題はポインタを利用すればいいということを学んだよ。類似の使い方をする問題も多そうな気がする。
- 前提として、循環していない場合のデータ構造はhead.next=Noneと考えた方が良さそう。
- 値だけで判別すると繋ぎ先があるように思えるが、データ構造としてはそれは誤り。⇦ここの誤解が今回解けなかった原因。
そもそものアプローチがズレてたのが悔しいですね...(´・ω・`)