Leet code 141. Linked List Cycleを解いてみた
目的
- 競プロの勉強の成果を図るべく、コーディング面接対策のために解きたいLeetCode 60問を解いた問題を解説していく
- せっかくなので60問解説できるように頑張る
- 今回は 「141. Linked List Cycle」をpython3で解いた
- といっても、python3 以外で解く予定は今のところないw
問題
日本語訳
Linked Listの先頭であるheadを指定して、Linked ListにCycle(= 閉路 )が含まれているかどうかを判断します。
次のポインタを継続的にたどることによって再び到達できるノードがリストにある場合、Linked ListにはCycleがあります。 内部的には、posは、tailの次のポインターが接続されているノードのインデックスを示すために使用されます。 posはパラメータとして渡されないことに注意してください。
Linked ListにCycleがある場合はtrueを返します。 それ以外の場合は、falseを返します。
前提知識
連結リスト(Linked List)
今回は「単方向連結リスト(singly-linked list)」を扱う
問題では、ListNodeが下記のように定義されており
- val: Nodeの値
- next: 次のListNode
で構成されている コードでは下記のようになる
# Definition for singly-linked list. class ListNode: def __init__(self, x): self.val = x self.next = None
イメージ図にすると下記のようになっており、ひたすらnextをたどり続け、 next = None となったら List の終端となる
Atcoderでは、pythonで標準で用意されている List のみ利用していたが、実際には 他言語 配列(array) に近いもので
例えば、index番号を指定して O(1) で値が取得できるといった特徴は Linked Listにはない機能であったりする
そのため、少し戸惑ったが、localで問題を解く環境を再現するために下記のようなコードを書いて対応した(leetcodeの問題を解く分には不要であるが、ローカル環境でdebugしたかったために作成した)
class LinkedList: def __init__(self): self.head = None def add(self, val: int) -> None: if self.head is None: self.head = ListNode(val) return cur = self.head while cur.next is not None: cur = cur.next cur.next = ListNode(val) def create_loop(self, pos: int) -> None: """ pos is 0-indexed """ if pos == 0: Exception("Couldn't create self-loop") cnt, cur = 0, self.head dep, end = None, None while cur: if cnt == pos: target = cur dep = cur cur = cur.next cnt += 1 if dep is None or target is None: Exception("Couldn't create loop") dep.next = target def show(self) -> None: cur = self.head while cur: print(cur.val) cur = cur.next
例えば、 add で値を Linked Listに追加する場合は、Headから値を辿り、 終端(next = None) の箇所を見つけたら ListNodeを作成し値を設定し、nextを更新する
create_loop では、pos(問題では与えられない) を指定し、終端を pos に連結する。posに相当する ListNodeは終端まで探索する途中に出現するので、出現した段階で保持しておく
当初のアプローチ
問題としては、Cycleの有無を判定すれば良いので、headから探索し、探索した ListNodeを set() で保持しておく
setは高速(平均 O(1))で、同一の要素があるかどうかを探索できるため、nextが既に探索済みであれば、それはCycle があると判断できると考えた
class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: """ Use hash table Time complexity: O(n) Auxiliary Space: O(n) """ cur, s = head, set([]) while cur: if cur in s: return True s.add(cur) cur = cur.next return False
コードとしては上記のようになる。
The number of the nodes in the list is in the range [0, 10^4] とあるので、 finds = [False] * pow(10,4) といったlistを用意しておき、探索した箇所をTrueにしていくといったアプローチでも同様に解くことができると思われる。
この際には、計算量としては O(N) になるが、set() に探索した ListNodeを保持するため、メモリ効率は悪い(O(N)) コードとなっている。
Follow up: Can you solve it using O(1) (i.e. constant) memory? とあるため、より不要な値を保持せず解く方法がないかを考えた。
フロイドの循環検出法 を用いたアプローチ
考えるにあたって、下記を見て様々な loop の検出方法があることを知る
その中に、フロイドの循環検出法(Floyd's cycle-finding algorithm) というものがあることを知る。 下記の、記事が非常にわかりやすいが、要はウサギ(1度に2step進む)と亀(1度に1step進む)を同時に、同じLinked List上を進ませた場合に、Cycleがある場合はウサギと亀はどこかのNode上で出会うといったことである。
コードに書き起こすと下記のようになるが、headもしくはhead.nextがNoneの場合はCycleは作成できないのでFalseとなる。 その後は、slow = head, fast = head.next として slowは1つづつ、fastは2つづつ進めていき、それぞれが同一のListNodeとなった段階でwhile文を抜けTrueを返すというコードを書いた
class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: if head is None or head.next is None: return False slow, fast = head, head.next while slow != fast: if slow.next is None: return False slow = slow.next for _ in range(2): if fast.next is None: return False fast = fast.next return True
2つのアプローチの結果
比較は下記になるが、Leetcodeでは提出のたびにRuntime(速度)もMemory(メモリ使用量)も変わるため、参考までに
- 当初のアプローチ: 52 ms 17.8 MB
- フロイドの循環検出法を用いた場合: 58 ms 17.5 MB
フロイドのアプローチの方がメモリ使用量が少ないことが伺える。 これは、保持する値がslow, fastでそれぞれ1 ListNode のみを保持するからだと考えられる。
まとめ
今回は、「141. Linked List Cycle」を解説してみた。 実際、解くことは簡単であった(easyなのでそれはそうなのだが)が、メモリ効率まで意識してAtcoderでは解いていなかったので良い経験になったのと LinkedListを自分で作ってみるみたいな経験は、今までしたことなかったので良い勉強になった。
解説したコードに関しては下記にあるので、もしローカルで動かしたい場合は利用してみると良いかもしれない。
次回は、「142. Linked List Cycle II」を解説してみようと思う。
