アルゴリズムのチェーンテーブルループ検出


問題の説明
ループチェーンテーブルが与えられ、アルゴリズムがループの先頭ノードを返すことを実現する.ループチェーンテーブルの定義:チェーンテーブル内のノードのnext要素がその前に現れたノードを指し、チェーンテーブルにループがあることを示します.
例1:入力:head=[1,2,3,4]、pos=1出力:tail connects to node index 1説明:チェーンテーブルにループがあり、その末尾が2番目のノードに接続されている.
例2:入力:head=[5,3]、pos=0出力:tail connects to node index 0解釈:チェーンテーブルにリングがあり、その末尾が最初のノードに接続されている.
例3:入力:head=[3]、pos=-1出力:no cycle解釈:チェーンテーブルにリングがありません.
要求空間複雑度o(1)
アルゴリズム実装
/**
 * Definition for singly-linked list.
 * 1.        ,     (fast     slow 2 )
 * 2.   fast   head  ,slow        ,         ,    ,          “      ”
 */ 
public class Solution {

    public ListNode detectCycle(ListNode head) {
        //     
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow==fast){
                break;
            }
        }
        //         NULL
        if(fast==null||fast.next==null){
            return null;
        }
        //               ,
        //             ,        
        fast = head;
        while(fast!=slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}