スポンサーリンク

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

スポンサーリンク
スポンサーリンク
この記事は約5分で読めます。

 

 

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

 

様々なカテゴリの問題をランダムにあたる方法も良いですが、

二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。

テーマごとに問題を分類しました。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

 

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

 

 

ポイント

    • 循環する連結リスト
    • two pointer

 

この記事で得られること

    • 連結リストの循環を判定できます。
    • two pointerの使い方の練習ができます。

 

 

詳細

 

問題

 

原文

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

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 (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

 

Example 1:

Example 2:

Example 3:

 

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.

 

 

内容(和訳)

連結リストheadが与えられるので、循環が始まるノードを返してください。
循環が無ければnullを返してください。
連結リストで継続的に次の要素に進んだ時に、再び同じ要素に到達できるとき循環があるといいます。
posは内部でtailの次のポインタ(循環が始まる要素)を示すために使われます。
posは0-インデックスで示され、循環がなければ-1になります。入力としては与えられます。

 

 

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

 

解答

 

解答1:Python , two pointer

 

two pointerを使います。

1つ進むslowと2つ進むfastポインタを無限に繰り返します。

循環があれば、いつかslowとfastは同じノードを指すので、その時点で無限ループを抜けます。

循環がない場合は、fastが連結リストの末尾(None)にたどり着きます。

 

循環がある場合は、slowとfastが一致したノードと、連結リストの先頭であるheadから同時に1つずつ進むことで、それらが一致したときに循環の開始ノードとなるので、そのノードを返します。(これは自分では気づけないと思いました。)

 

 

 

終わりに

補足・参考・感想

 

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

 

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

 

 

疑問が解決した方は他の問題もどうぞ

前:206. Reverse Linked List

次:102. Binary Tree Level Order Traversal

LeetCode 解答・解説記事一覧

 

 

疑問が解決しない方はこちらへ

・連結リストを作るためのListNodeクラスがありますが、クラスに初めて触れる方はこちらへどうぞ。

Pythonのクラスの概要と使い方を整理

 

・連結リストについてまとめたページもあります。

連結リストの概要・イメージ・実装・使い方を整理

 

 

 

コメント