AcWing 34. 链表中环的入口结点
原题链接
中等
作者:
不幸到吃土
,
2025-01-09 20:35:47
,
所有人可见
,
阅读 2
//以下分析基于y总题解的图
/*
设快慢指针于点c处相遇,另设a到b的距离为x,b到c的距离为y (其中b为环的入口节点)
接下来"倒着想":当慢指针走到b的时候,快指针相应倒退2y距离,令此时快指针所处位置为d
不难发现:d到b的距离为y,且慢指针由a到b走了x,快指针由a到d走了2x → 故b到d的距离为x
简单计算可得:c到b的距离为:环形周长(x+y) - b到c的距离 = x
故:令慢指针指向a,快指针指向c,此时按相同步伐重新遍历,再次相遇时即为环的入口处
*/
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *entryNodeOfLoop(ListNode *head) {
if(!head || !head->next) //若头结点为空或链表为空
return 0;
ListNode *i = head , *j = head; //i表示慢指针,j表示快指针
while(i && j){ //i、j均不指向NULL
i = i->next;
j = j->next;
if(j){
j = j->next;
}else{
return 0;
}
if(i == j){ //快慢指针相遇
i = head;
while(i != j){
i = i->next;
j = j->next;
}
return i;
}
}
return 0;
}
};