【LeetCode】141. Linked List Cycle 解答・解説【Python】

この記事は約4分で読めます。

 

問題

原文

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

 

Example 1:

Input: head = [3,2,0,-4], pos = 1

Output: true

Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0

Output: true

Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1

Output: false

Explanation: There is no cycle in the linked list.

 

Constraints:

  • The number of the nodes in the list is in the range [0, 104].
  • -105 <= Node.val <= 105
  • pos is -1 or a valid index in the linked-list.

 

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

 

内容

連結リストの先頭であるheadが与えられます。循環リストであるか判定してください。リスト内をポインタを継続的に追うことで再び到達できるノードがある時に循環があるといえます。内部的にはposはtailの次のポインタが指すノードのインデックスを示すために使われます。posはパラメータ(問題の入力)としては渡されません。

連結リスト内に循環があればTrue、なければFalseを返してください。

※正しくない可能性があります。

方針

・連結リスト内に循環があるかを調べるテクニックとしてスロー・ファストの2つのポインタをつかうという方法があるようです。

解答

解答1:

 

解答2:setを使用

 

解答3:2ポインタを使用

 

 

補足・参考・感想

参考

【データ構造】連結リスト・ランナーテクニックを解説!【頻出問題】 (suwaru.tokyo)

Linked List Cycleを理解する – Qiita

Fast and slow pointer technique in Linked List (opengenus.org)

 

連結リストに循環があるかを調べる方法にfast,slow pointer(tortoise and hare algorithm,フロイドの循環検出法)というテクニックがあることを知ることができた。ただ、そもそも連結リストの扱いに慣れていないので、先に連結リストについてしっかりと勉強する必要がある。

 

前:136. Single Number

次:217. Contains Duplicate

LeetCode 解答・解説記事一覧

コメント