[leetcode] [python] 142。リンクリストサイクルII

142

---

Knowledge points: two pointers

1.元のタイトル

リンクリストを指定して、サイクルが開始するノードを返します。サイクルがない場合は、nullを返します。

指定されたリンクリストのサイクルを表すために、テールが接続するリンクリストの位置（0インデックス）を表す整数posを使用します。 posが-1の場合、リンクリストにサイクルはありません。

注：リンクリストは変更しないでください。

例1：

入力：head = [3,2,0、-4]、pos = 1
出力：テールはノードインデックス1に接続します
説明：リンクリストに、テールが2番目のノードに接続するサイクルがあります。

例2：

入力：head = [1,2]、pos = 0
出力：テールはノードインデックス0に接続します
説明：リンクリストに、テールが最初のノードに接続するサイクルがあります。

例3：

入力：head = [1]、pos = -1
出力：サイクルなし
説明：リンクリストにサイクルがありません。

ファローアップ：
余分なスペースを使わずに解決できますか？

2.タイトル

リストにリングがあるかどうかを判断します。ある場合はリングの開始点に戻り、ない場合は[なし]を返します。

3.アイデア

リングがあるかどうかだけを判断する場合は、高速ポインタを一度に2ステップ、低速ポインタを一度に1ステップずつ移動させることができます。 2つのポインタが等しい限り、リングがあります。
ただし、リングの開始点を見つける必要がある場合は、それを分析する必要があります。 （写真はNan Guo Ziqiからのものです、ありがとうございます）

まず、2つのポインターが合流して、写真の合流点であるリングがあるかどうかを判断するように、2ステップ速く、1ステップ遅くするというアイデアを採用します。会議時に、低速ポインタはk + Mの距離を移動し、高速ポインタはk + M + nを移動します。 L、nの距離は、さらに進むためのラップ数です。
2（k + M）= k + M + n L
k = n * L-M
したがって、会議後、低速ポインターを頭に戻すと、高速ポインターは、減算された距離Mを表すために会議ポイントに留まります。その後、高速ポインターと低速ポインターが段階的に実行されます。 2つのポインターが出会うとき、それは出発点です。

4.コード

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def detectCycle(self, head): ''' :type head: ListNode :rtype: ListNode ''' if head==None or head.next==None: return None f=s=head while f and f.next: f=f.next.next s=s.next if f==s: break if f==s: s=head while f!=s: f=f.next s=s.next return s return None

5.リファレンス

https://www.cnblogs.com/zuoyuan/p/3701877.html