題目描述
給定一個(gè)鏈表瘟裸，返回鏈表開(kāi)始入環(huán)的第一個(gè)節(jié)點(diǎn)浴韭。 如果鏈表無(wú)環(huán)丘喻，則返回 null。
說(shuō)明：不允許修改給定的鏈表囱桨。
進(jìn)階：
你是否可以不用額外空間解決此題仓犬？
分析
用雙指針遍歷求相交的節(jié)點(diǎn)。
慢指針和快指針的初始位置是：head
慢指針一次前進(jìn)一步舍肠，快指針一次前進(jìn)兩步搀继。
兩個(gè)指針相交的節(jié)點(diǎn)為C。
設(shè)非循環(huán)鏈表部分為X,循環(huán)鏈表中C節(jié)點(diǎn)之前的部分為Y ,C之后的部分為Z,可以根據(jù)快指針和慢指針經(jīng)過(guò)的節(jié)點(diǎn)數(shù)列出方程：
2*（X + Y） = X + Y + Z + Y
解方程得到：X = Z
讓慢指針從C節(jié)點(diǎn)出發(fā)翠语，快指針從head出發(fā)叽躯，一次前進(jìn)一步，相等的節(jié)點(diǎn)為入環(huán)的第一個(gè)節(jié)點(diǎn)
方程左邊的慢指針遍歷的節(jié)點(diǎn)數(shù)肌括，右邊為快指針遍歷的節(jié)點(diǎn)數(shù)点骑，
鏈表：
1 -> 2 -> 3 -> 4,循環(huán)節(jié)點(diǎn)為3,
慢指針遍歷的節(jié)點(diǎn)是：2,3
快指針遍歷的節(jié)點(diǎn)是：2,3,4,3
起始位置的節(jié)點(diǎn)不算
相交的節(jié)點(diǎn)是:3
X = 2
Z = 4
Y = 3
代碼
/**
* 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) {
if(head == NULL) {
return NULL;
}
auto slow = head;
auto quick = head;
bool circle = false;
while(quick != NULL && quick->next != NULL) {
slow = slow->next;
quick = quick->next->next;
if(quick == slow){
circle = true;
break;
}
}
if(!circle) {
return NULL;
}
quick = head;
while(slow != quick) {
slow = slow->next;
quick = quick->next;
}
return slow;
}
};
題目鏈接
https://leetcode-cn.com/explore/interview/card/tencent/222/linked-list/917/
