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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/

//从距离相等->联想到单步走遍历
//如果在某点相等，如果单步遍历，则必定是不断重叠走到相等点
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {

        if(pHead==nullptr||pHead->next==nullptr){
            return nullptr;
        }
        ListNode * slow=pHead->next;
        ListNode * fast=pHead->next->next;

        while(fast!=nullptr&&fast!=slow){
            if(fast->next!=nullptr){
                fast=fast->next->next;
                slow=slow->next;
            }
            else{
                fast=nullptr;
            }
          
        }

        if(fast==nullptr){
            return nullptr;
        }

        for(slow=pHead;slow!=fast;){
            slow=slow->next;
            fast=fast->next;
        }

        return fast;
    }
};

1.得出了nt=x之后，意味着重新分头遍历，可以在重叠部分反复重叠

2.实现时，先处理

2.1 开头

2.2 遍历时边界条件，包括fast->next，fast->next->next

2.3 while的条件