链表中环的入口结点

题目描述

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

代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        //两个指针,一个每次走一步,一个走两步,有环肯定会相遇,如果第一次指针走了X步就相遇了,那第二个指针就是走了2X步，多走了X步肯定是在环里，
        //第一个指针重新指向头部，两次指针每次都一步，相等的时候就是环的入口
        if (pHead == NULL || pHead->next == NULL) {
            return NULL;
        }
        ListNode *r1 = pHead->next, *r2 = pHead->next->next;
        while (r1 != NULL && r2 != NULL && r2->next != NULL && r1 != r2) {
            r1 = r1->next;
            r2 = r2->next->next;
        }
        
        r1 = pHead;
        while (r1 != r2) {
            r1 = r1->next;
            r2 = r2->next;
        }
        return r1;
    }
};