題目如下：

解題過(guò)程如下：

思路：快慢指針在環(huán)里一定會(huì)相遇，相遇結(jié)點(diǎn)到入環(huán)起始結(jié)點(diǎn)的距離 == 鏈表頭結(jié)點(diǎn)到入環(huán)起始結(jié)點(diǎn)的距離（距離看從左往右的方向，也就是單鏈表的方向），從鏈表頭結(jié)點(diǎn)和相遇結(jié)點(diǎn)遍歷，只要結(jié)點(diǎn)一樣，那么這個(gè)結(jié)點(diǎn)就是入環(huán)起始結(jié)點(diǎn)。

示例1、示例2為例，

示例1：相遇結(jié)點(diǎn)到入環(huán)起始結(jié)點(diǎn)的距離1 == 鏈表頭結(jié)點(diǎn)到入環(huán)起始結(jié)點(diǎn)的距離1

示例2：相遇結(jié)點(diǎn)到入環(huán)起始結(jié)點(diǎn)的距離0 == 鏈表頭結(jié)點(diǎn)到入環(huán)起始結(jié)點(diǎn)的距離0

完整代碼如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {//快慢指針ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;//快慢指針相遇if (slow == fast){//鏈表頭結(jié)點(diǎn)和相遇結(jié)點(diǎn)開(kāi)始往后遍歷，結(jié)點(diǎn)一樣，這個(gè)結(jié)點(diǎn)就是入環(huán)起始結(jié)點(diǎn)ListNode* pcur = head;while (slow != pcur){slow = slow->next;pcur = pcur->next;}return slow;}}//fast == NULL 或 fast->next == NULL，跳出循環(huán)，說(shuō)明沒(méi)有環(huán)return NULL;
}

試著證明：

為什么在帶環(huán)鏈表中，鏈表的頭結(jié)點(diǎn)和快慢指針相遇結(jié)點(diǎn)到入環(huán)起始結(jié)點(diǎn)的距離相等？

假設(shè)：鏈表的頭結(jié)點(diǎn)到入環(huán)起始結(jié)點(diǎn)的距離是L，環(huán)的周長(zhǎng)是R，若slow剛剛?cè)氕h(huán)時(shí)fast已經(jīng)在環(huán)里繞了n圈了（n至少為1，因?yàn)閒ast先進(jìn)環(huán)中到M點(diǎn)，后又和slow在M點(diǎn)相遇），入環(huán)起始結(jié)點(diǎn)到相遇結(jié)點(diǎn)之間的距離是X。

慢指針進(jìn)環(huán)后，快指針肯定會(huì)在慢指針走一圈之內(nèi)追上慢指針。因?yàn)樵诳炻羔樁歼M(jìn)環(huán)之后，快慢指針之間的距離最多就是一個(gè)環(huán)的周長(zhǎng)，快指針每追擊1次，二者之間的距離就會(huì)縮小1步，所以，在慢指針移動(dòng)一圈之前，快指針一定會(huì)追上慢指針。

若已經(jīng)相遇，快慢指針走過(guò)的路程：
慢指針 = L + X
快指針 = L + X + nR

由于快慢指針走過(guò)的路程之間的關(guān)系2 * 慢指針 = 快指針，得出L = nR - X = (n - 1)R + R - X，式子L = (n - 1)R + R - X（n為1，2，3，4，……，n的大小取決于環(huán)的大小，環(huán)越大n越小）中，(n - 1)R表示繞(n - 1)圈，取極端情況，n = 1時(shí)，式子最終可以看成L = R - X，即slow指針從鏈表起始位置開(kāi)始向后遍歷，fast指針在相遇點(diǎn)開(kāi)始環(huán)繞，最終一定會(huì)在入環(huán)起始結(jié)點(diǎn)相遇；也就是說(shuō)，在帶環(huán)鏈表中，鏈表的頭結(jié)點(diǎn)和快慢指針相遇結(jié)點(diǎn)到入環(huán)起始結(jié)點(diǎn)的距離相等。