leecode 解题总结：142. Linked List Cycle II

#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;}