[数据结构与算法]【剑指offer】＜easy＞【JZ23 链表中环的入口结点】

v1

首先很简单的想到用list存一下每一个遍历的结点，然后在访问到下一个结点的时候，
都去检查这个结点是否在list中出现过，但是这样复杂度是O(n^2)

class Solution:
    def EntryNodeOfLoop(self, pHead):

        ls = []
        while pHead:
            ls.append(pHead)
            if pHead.next in ls:
                return pHead.next
            pHead = pHead.next
        return None

评价：

• 这样虽然写下来很简洁，但是运行速度超级慢。
• 优化方式： 集合set(查询快）、快慢指针https://blog.csdn.net/N1314N/article/details/90736225

v2 – set方法

class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        visited = set()
        while pHead:
            if pHead in visited:
                return pHead
            visited.add(pHead)
            pHead = pHead.next

v3 – 快慢指针

原理其实挺简单，就是两个指针，一个快一个慢，只要有速度差，如果是环最终就会相遇。
由于速度是t:2t，所以最终路程是i:2i，环的长度刚好是i。
利用从头结点创建的cur，和slow逐步往前，最后cur到循环结点时，slow由于始真快l的路程，所以刚好会相遇。

    def EntryNodeOfLoop(self, pHead):
        # write code here
        slow = pHead
        fast = pHead
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                break
        if not fast or not fast.next:
            return
        cur = pHead
        while cur != slow:
            cur = cur.next
            slow = slow.next
        return cur