【LeetCode】141. Linked List Cycle（Easy）

【最初に】

LeetCode 5個目に挑戦です

【問題】

与えられたLinkedListが循環しているかどうか判定せよ

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

【1.とりあえず】

ぱっと思いついたのは、LinkedListをループさせて可変長配列に詰めていく。過去のノードと同じノードが出てきたら循環参照していると判定する。

f:id:ninagreen:20191110025557p:plain

できた！

f:id:ninagreen:20191110025956p:plain

【2.違うパターン】

問題文の最後に

Can you solve it using O(1) (i.e. constant) memory?

とあるので、空間計算量がO(1)になるように考えてみる（今はLinkedListを全件ループして配列に格納しているのでO(n)になっている）

時間計算量はO(n)→O(n^2) になっちゃうけど、とにかく保存せずにループ回しまくってみる。

f:id:ninagreen:20191110031450p:plain

ひどいコードだけど一応できた！

f:id:ninagreen:20191110031549p:plain

【3.解答を見てみる】

2つの異なるスピードのポインターを持てばいいのでは？とあるが、個人的にはなかなか馴染みのない考え方。要は足の速い選手と遅い選手がいて、遅い選手が1進むたびに速い選手が2進むとすると、循環参照していた場合、足の速い選手が1ずつ周回遅れの遅い選手との距離を縮めて行っていつか追いつくというもの。やってみた。

f:id:ninagreen:20191110034015p:plain