連結リストの先頭ノード head が与えられた場合、リスト内のループが開始する最初のノードを返します。リストにループがない場合は null を返します。

あるノードから next ポインタをたどることで再びそのノードに到達できる場合、リストにはループが存在します。評価システムは内部的に整数 pos を使用してリストの末尾が接続されている位置を示します（インデックスは0から始まります）。pos が -1 の場合、そのリストにはループがありません。注：pos はパラメータとして渡されません。これはリストの実際の状態を識別するためだけに使用されます。

リストの変更は許可されていません。

例 1：

<strong>入力：</strong>head = [3,2,0,-4], pos = 1
<strong>出力：</strong>インデックス1のノードを返す
<strong>説明：</strong>リストにはループがあり、末尾が2番目のノードに接続されています。

例 2：

<strong>入力：</strong>head = [1,2], pos = 0
<strong>出力：</strong>インデックス0のノードを返す
<strong>説明：</strong>リストにはループがあり、末尾が最初のノードに接続されています。

例 3：

<strong>入力：</strong>head = [1], pos = -1
<strong>出力：</strong>nullを返す
<strong>説明：</strong>リストにはループがありません。

制約：

• リスト内のノード数の範囲は [0, 104] です
• -105 <= Node.val <= 105
• pos の値は -1 またはリスト内の有効なインデックスです

発展問題： O(1) の空間複雑度でこの問題を解決できますか？

    /**
     * rabbitの移動距離はtortoiseの2倍、つまり r=2t
     * rabbitはtortoiseよりループの長さをn周多く進んでいる、つまり r=t+nl
     * 上記2式から r=2nl、t = nlが導かれる
     * つまりrabbitとtortoiseはそれぞれ2n周、n周進んだことになる
     * @param head
     * @return
     */
    public ListNode findCycleStart(ListNode head) {
        ListNode rabbit = head, tortoise = head;
        while (true) {
            if (rabbit == null || rabbit.next == null) {
                return null;
            }
            rabbit = rabbit.next.next;
            tortoise = tortoise.next;
            // 最初の交差点を作る
            if (tortoise == rabbit) break;
        }
        // ループ入口までの歩数は：k=a+nl
        // ここでaの歩数を求めれば、ループ入口のノードが特定できる
        rabbit = head;
        while (tortoise != rabbit) {
            tortoise = tortoise.next;
            rabbit = rabbit.next;
        }
        // この時点で交差点がループの開始ノード
        return rabbit;
    }