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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode *slow=pHead, *fast=pHead, *iter = pHead,*next;
        bool is_ring = false;
        if(pHead->next==nullptr||pHead->next==nullptr||pHead->next->next==nullptr) return nullptr;
        fast = pHead->next->next;
        while(slow&&fast->next&&fast->next->next){
            if(slow==fast) {
                is_ring = true;
                break;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        if(is_ring==false) return nullptr;
      	//上面代码判断是否有环，如果没有环，那么一定没有环的入口节点，返回nullptr
      	
      	//然后判断入口节点，思路是一个一个断开节点，那么断到最后的节点就是入口节点。
      	//缺点是破坏了原链表，不知道算不算作弊
        next = pHead->next;
        while(next){
            iter->next = nullptr;
            iter = next;
            next = next->next;
        }
        return iter;
    }
};