#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*問題:Given a linked list, return the node where the cycle begins. If there is no cycle, return null.Note: Do not modify the linked list.Follow up:Can you solve it without using extra space?分析:給定一個鏈表，返回環開始的那個節點，如果沒有環，返回空。不要修改鏈表。這個就需要用到環開始的距離特點了。那個公式要推演出來，有點復雜。如果相遇后，再次相遇，統計所走的步數就是環的長度。對于求環的長度有用。假設環的起點為x,第一次相遇的時候總共走的步數為S，設環的長度為C那么第一次相遇的點: y=(S - x) % C  + x記得答案是C-那么滿指針走的步數。參見這一位的解法:http://blog.csdn.net/u014248312/article/details/51712554設起鏈表頭結點到環形起始點距離:a,兩者相遇的點距離環形起始點距離:b相遇點到環形起始點距離為c:則有如下等式成立:滿指針走的總步數=a + b快指針走的總步數=a + b + n*(b+c)，C為環形長度2(a + b) = a + b + n*(b+c)所以a+b=n*(b+c),n可以為1,2...為了求出n,所以c=(a+b)/n - b > 0,這里如果我們選取n=1，則有c=a,也就是從相遇點開始，一個指針從起點走，一個結點從相遇點走必定相遇在環形起點報錯:More Details Last executed input:[1,2]tail connects to node index 0超時了，1->2,2->1這種的時候，快慢指針定位于2結點相遇然后slow從2開始，初始結點從1開始永遠不能相遇1沒有環，關鍵:1 設從首結點到環形起點距離a,環形起點到相遇點距離b,相遇點到環形起點距離為c2(a+b)=a + b + n*(b+c)c=(a+b)/n - b，為了確保c>0,取n=1,c=a,表明從相遇點開始，慢指針每次走一步，首結點每次走一步最終相遇的地方就是環形起點。2 //ListNode* fast = head->next;//這里的快指針也必須從頭結點開始，而不是從下一個結點開始這樣就必須把判斷相等的條件放在后面ListNode* fast = head;ListNode* slow = head;*/struct ListNode {     int val;     ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};class Solution {public:    ListNode *detectCycle(ListNode *head) {        if(!head)		{			return NULL;		}		//ListNode* fast = head->next;//這里的快指針也必須從頭結點開始，而不是從下一個結點開始		ListNode* fast = head;		ListNode* slow = head;		bool isFind = false;		while(fast && slow)		{			slow = slow->next;			if(fast->next)			{				fast = fast->next->next;			}			//為空了，說明沒有環			else			{				break;			}			if(fast == slow)			{				isFind = true;				break;			}		}		//如果沒有環，		if(!isFind)		{			return NULL;		}		//有環：就快慢指針相遇后，慢指針和首指針一起每次一步相遇的地方就是		ListNode* newHead = head;		while(newHead && slow)		{			if(newHead == slow)			{				return newHead;			}			newHead = newHead->next;			slow = slow->next;		}		return NULL;    }};void PRint(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<int> nums;	 int value;	 int num;	 Solution solution;	 vector<int> result;	 while(cin >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}