title: 链表中环的入口结点
date: 2023-07-25 11:57:00
tags:
- c/c++
categories:
- 算法
- 笔试
top:
链表中环的入口结点
题目来自acwing
题目（点击跳转）
给定一个链表，若其中包含环，则输出环的入口节点。
若其中不包含环，则输出null。
数据范围
节点 val 值取值范围 [1,1000]。
节点 val 值各不相同。
链表长度 [0,500]。
样例
给定如上所示的链表：
[1, 2, 3, 4, 5, 6]
2
注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。
则输出环的入口节点3.
思路：
双指针实现，定义两个指针，first和second，同时从链表头部开始走，first每次走一步，second每次走两步，当second遇到NULL时代表链表走到尽头，即没有环。当两个指针第一次相遇时，将first重置为头节点的位置，second位置不变，这时让两个指针都已每次一步的距离开始走，当两个指针再次相遇时，这个点就是环的入口。
证明：假设b点为环的起点，当first和second从a开始出发，当first走到b时，first走了距离x，second走过了first两倍的路程，即为2x，second可能在环上已经走过一圈以上，这次加入first再走y距离与second相遇，那么second走的距离即为2y，也就是说当first在b时，second与b的距离为y，那当second走出了b点距离为y时，在环上再走距离x必定可以回到b点，那么将first从头节点开始走x，此时与second第二次相遇即为环的开始节点。
代码：
/**
* 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 NULL;
auto first = head, second = head;
while(first && second) {
first = first->next;
second = second->next;
if(second) second = second->next;
else return NULL;
if(first == second){
first = head;
while(first != second){
first = first->next;
second = second->next;
}
return first;
}
}
return NULL;
}
};