c++ 刷题 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。心得

题目描述：

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

我的思路：

起初我是想：
链表无非是有环和无环两种情况因此
1 遍历每一个链表结点，并把节点的地址存到一个vector数组里
2 遍历新的结点时判断该节点是否在数组里

这个思路应该行得通，但是最坏情况下的时间复杂度：o(n^2)阶，因为每输入一个元素都得与保存节点的数组比较看是否重复。

思路通不代表能行，在写代码时遇到的指针的存储类型的问题，使用int型指针报错，网上搜也没找到什么类型的变量能存储指针的地址（指针又不能放进数组里。。。），因此去看了看题解。

题解：

看来又是一个数学问题。。。
我把他的代码自己实现了一下：

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        //定义快慢指针
        ListNode*fast=pHead,*low=pHead;
        //遍历链表，当遇到尾指针的时候退出
        while(fast != NULL && fast->next != NULL){
            //快指针走两步，慢指针走一步
            fast=fast->next->next;
            low=low->next;
            //快慢指针相遇
            if(fast==low)
                break;
        }
        //尾指针存在返回NULL
        if(fast == NULL || fast->next == NULL)
        	return NULL;
        	
        low=pHead;//low从链表头出发
        while(fast!=low){//fast从相遇点出发
            fast=fast->next;
            low=low->next;
        }
        return low;
    }
};

结果：

小结：

1、看到问题不要立刻思考它的程序步骤，应该思考它的数学解题方法
2、vector容器的添加新元素过程：建立size+1的vector容器，旧的容器复制到新的容器，并在新容器尾部加入新元素，释放旧的容器
3、线性存储结构的数组大小只要确定了就不可更改