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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        // 创建一个新节点node，遍历链表，然后让遍历过的链表的next指向node，
        // 若存在环，则环的入口节点一定会被遍历两次
        // 判断每个节点的next，如果next等于node，则这个节点便是环的入口节点
        ListNode* node = new ListNode(-1);
        auto cur = pHead;
        while(cur) {
            auto pre = cur->next;
            if(pre == node)
                return cur;
            cur->next = node;
            cur = pre;
        }
        return NULL;
    }
};