力ボタン142.リングチェーンテーブルII

力ボタン142,142.リングチェーンテーブルIIは、チェーンテーブルが与えられ、チェーンテーブルがリングに入り始める最初のノードを返す.チェーンテーブルにループがない場合はnullを返します.
与えられたチェーンテーブルのループを表すために、整数posを使用してチェーンテーブルの最後にチェーンテーブルに接続された位置を表します(インデックスは0から始まります).posが-1の場合、チェーンテーブルにリングはありません.
説明:指定したチェーンテーブルの変更は許可されていません.
例1:
入力:head=[3,2,0,-4],pos=1出力:tail connects to node index 1解釈:チェーンテーブルにループがあり、その末尾が2番目のノードに接続されています.
例2:
入力:head=[1,2]、pos=0出力:tail connects to node index 0解釈:チェーンテーブルにループがあり、その末尾が最初のノードに接続されています.
例3:
入力:head=[1]、pos=-1出力:no cycle解釈:チェーンテーブルにリングがありません.
2つのポインタ、速いポインタと遅いポインタ、速いポインタで2ステップずつ移動し、遅いポインタで1ステップずつ移動し、両者が出会うとループを終了し、ノードと出会い点から1ステップの速度で移動し、両者が出会うとループの起点となる.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
     ListNode *detectCycle(ListNode *head) {
   ListNode*fast=head;
   ListNode*slow=head;
   ListNode*meet=NULL;
   while(fast){
   	 slow=slow->next;
   	 fast=fast->next;
   	 if(!fast){
   	 	return NULL;
	}
	fast=fast->next;
   	 if(slow==fast){
   	 	     meet=fast;
   	 	     break;
	 }
   }
   if(meet==NULL)return NULL;
   while(head&&meet){
   	  if(head==meet){
   	  	return head;
	}
	head=head->next;
	meet=meet->next;
   }
   return NULL;
}
};