题目描述 [链表中环的入口结点]
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
解题思路
- 使用快慢指针找到环的相汇点 p1每次走一步,p2每次走两步,直到p1==p2
- 找环的入口,当p1==p2,p2所经过节点数为2x, p1所经过节点数为x, 设环中有n个节点, p2比p1多走一圈有 2x=n+x; 则 n=x,可以看出p1实际走了一个环的步数,再让p2指向链表头部,p1位置不变,p1,p2每次走一步直到p1==p2; 此时p1指向环的入口。
代码
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if(pHead==nullptr) return nullptr;
ListNode *p1=pHead;
ListNode *p2=pHead;
while(p1 && p2->next){
p1 = p1->next;
p2 = p2->next->next;
if(p1==p2){
p2=pHead;
while(p1!=p2){
p1 = p1->next;
p2 = p2->next;
}
if(p1==p2) return p1;
}
}
return nullptr;
}
};