题解 | 链表中环的入口结点

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* fast = pHead;
        ListNode* slow = pHead;

        if (fast->next == nullptr)
            return nullptr;
        if (fast->next->next == nullptr)
            return nullptr;


        fast = fast->next->next;
        slow = slow->next;
        while (fast != nullptr) {
            if (fast == slow) {
                ListNode* gen1 = pHead;
                ListNode* gen2 = fast;

                while (gen1 != gen2) {
                    gen1 = gen1->next;
                    gen2 = gen2->next;
                }

                return gen2;
            } else {
                // if the size of the linked list is odd number
                if (fast->next == nullptr)
                    break;
                fast = fast->next->next;
                slow = slow->next;
            }
        }

        // if there is nullptr, there is null
        return nullptr;
    }
};

这个问题主要的问题有两个

1. 检查是否有环
2. 找到环的入口点

检查环的存在，就需要用到快慢指针（一个速度2，一个速度1）。快指针终归会追上慢指针，如果追上了就是速度只差1，而且通过实践可以知道，即使是最坏的情况，也就是快指针入圈的时候比慢指针多了一格，快指针也能追上。

快慢指针相等，证明环存在。存在之后我们需要找到入口。

数学推导

这里的x=z我们就可以在当前的基础上，设置两个步长为1的指针去移动，相遇的时候就是环的入口#剑指offer#