环链找起点（快慢指针）

问题描述如下：

给定一个有环的链表，求开始进入环的那个结点，即下图的 target 。

分析：

这个问题可以使用快慢指针来巧妙解决，快指针 fast 每次移动两个结点，

慢指针 slow 每次移动一个结点。

当 slow 和 fast 相遇的时候，slow —> target = head —> target = k

即慢指针和头结点到 target 的距离相同。

这个时候 head 和 slow 一起往后移动，当它们相遇的时候，正好在 target 。

现在的问题是“当 slow 和 fast 相遇的时候，slow —> target = head —> target = k”这个结论是如何得到的。

设 fast 和 slow 相遇的时间为 t，slow 的速度为 1，fast 的速度为 2，

当 slow 和 fast 相遇的时候，fast 多走了一个环，设环的长度为 L 。

即 2 * t - 1 * t = L => t = L

故 slow 走的路程 s = vt = 1*t = t = L

已知 head 到 target 的距离为 k，则 slow 逆向到达 target 的距离为 L-k

而环的长度为 L，因此 slow 正向到达 target 的距离为 L - (L - k) = k

因此 slow —> target = head —> target = k 得证。

参考代码：

// 记录博客！求有环链表起点 快慢指针相遇时 他们与环起点的距离=head与环起点的距离 
#include<iostream>
using namespace std;

struct NODE {
	int data;
	NODE *next;
	NODE(){
		data = 0;
		next = NULL;
	}
	NODE(int n){
		data = n;
		next = NULL;
	}
};

// 很巧妙 快慢指针相遇的时候距离起点是k head距离起点也是k 
int getResult(NODE *head){
	NODE *fast = head->next, *slow = head->next;
	do{
		fast = fast->next->next;
		slow = slow->next;
	}while(fast != slow);
	NODE *p = head->next;
	while(p != slow){
		p = p->next;
		slow = slow->next;
	}
	return p->data;
}

int main(){
	int n;
	while(cin >> n){
		int begin;
		cin >> begin;
		NODE *head = new NODE();
		NODE *pre = head;
		NODE *p = head;
		for(int i = 0; i < n; i++){
			int in;
			cin >> in;
			p->next = new NODE(in);
			p = p->next;
			if(begin > 0){
				begin--;
				pre = p;
			}
		}
		p->next = pre;
		int ans = getResult(head);
		cout << ans << endl;
	} 
	return 0;
}

【END】感谢观看