剑指Offer-23-链表中环的入口结点

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

图解

Code

//a=(k-1)(b+c)+c 这个式子的意思是： 链表头到环入口的距离=相遇点到环入口的距离+（k-1）圈环长度。其中	k>=1,所以k-1>=0圈。所以两个指针分别从链表头和相遇点出发，最后一定相遇于环入口。
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {    
        if(!pHead)
            return 0;
        
        //设置快慢节点
        ListNode* Fp=pHead,*Sp=pHead;
        //1.判断有无环
        while(Fp!=0&&Fp->next!=0){
            Fp=Fp->next->next;
            Sp=Sp->next;
            if(Fp==Sp)
                break;
        }
        //快指针为空，则无环
        if(!Fp||!Fp->next)
            return 0;
        
        //再将快指针指向链头，必定可以相遇
        Fp=pHead;
        while(Fp!=Sp){
            Fp=Fp->next;
            Sp=Sp->next;
        }
        return Fp;
    }
};