链表中环的入口节点

链表中环的入口节点

题目描述

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

解题思路

• 首先判断是否有环，用iscircle函数实现。快慢指针，快指针能追上慢指针就表示有环，返回两个指针接触时的节点，否则就表示无环，返回NULL。
• 判断有环后，用两个指针，分别从链表头和iscircle返回的节点开始同步遍历，两个指针相相遇的节点就是链表中环的入口节点。

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        ListNode *meetnode = iscircle(pHead);
        if(meetnode==NULL) return NULL;
        ListNode *p1=meetnode,*p2=pHead;
        while(p1 != p2){
            p1=p1->next;
            p2=p2->next;
        }
        return p1;
    }
    ListNode *iscircle(ListNode *pHead){
        if(pHead==NULL || pHead->next==NULL)
            return NULL;
        ListNode *p=pHead,*q=pHead;
        while(p!=NULL && q!=NULL){
            p=p->next;
            q=q->next;
            if(p!=NULL)
                p=p->next;
            if(p==q)
                return p;
        }
        return NULL;
    }
};