剑指offer-55：链表中环的入口结点

目录

剑指offer-55链表中环的入口结点目录 1题目描述2题目解析3题目答案

1题目描述

一个链表中包含环，请找出该链表的环的入口结点。

2题目解析

3题目答案

class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead){ if(pHead==NULL||pHead==NULL) return NULL; ListNode* p1=pHead; ListNode* p2=pHead; while(p2!=NULL && p2->next!=NULL){ //p2一直没有尾部节点 p1 = p1->next; p2 = p2->next->next; //p2是p1速度的二倍 if(p1==p2){ //当p1、p2相遇时，p1不变，p2指向起点 p2 = pHead; while(p1!=p2){ p1=p1->next; p2=p2->next; } if(p1==p2) //当p1、p2再次相遇时，即为环的入口节点 return p1; } } return NULL; } };