题解 | #链表中环的入口结点# 标记法（特殊解法）

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if(!pHead) return nullptr;	//特殊情况，加这一行可以提高效率，不加程序也可以正常运行
	  
        // 思路：设置一个flag标记节点，如果每个节点时，做标记，将走过的节点的next标记为flag
        auto flag = new ListNode(-1);
        auto cur = pHead;
        while(cur){
            if (!cur->next) {
                return nullptr;
            } else {
                if (cur->next == flag) {
                    break;
                }else {
				  	//进行flag标记
                    auto next_temp = cur->next;//设置一个临时变量，保存下一个节点的位置
                    cur->next = flag; //破坏链表连接，将走过的节点都指向flag
                    cur = next_temp;
                } 
            }
        }
        return cur;
    }
};

思路：遍历列表，每走过一个节点，就将该节点指向一个特殊的flag，从而证明该节点已经被走过。通过该过程，环被破坏，遍历到的最后一个节点就是环起始的位置。

优势：时间复杂度为n，速度快，代码简短易懂

劣势：破坏了链表结构，虽然找到了环，但也导致该链表不可用，同时大量的节点未被回收