剑指 链表环的入口

通过指针方法，设置快慢指针，快指针每次前进两个节点，慢指针每次前进一个节点，当他们第一次相遇后，证明链表中存在环，然后将快指针置为头指针，慢指针与快指针继续每次前进一个节点，当他们再次相遇，就是换的入口位置。如果快慢指针从不相遇，快指针会走到链表结尾，那么就不存在环。O(n)

快指针走了n(n >= 1)圈后与慢指针相遇，
固有：
2(A + B) = n(B+C)+B+A
A = nC+(n-1)B
A = C + (n-1)(C+B)
因为C+B为一圈的长度，所以用c， h两个指针从p点和head开始走，当h走完A时，c走过的路为C + (n-1)(C+B)，即n圈+C，所以h和c的相遇点为q

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        quick=slow=pHead
        if quick==None :
            return None
        while quick!=None and quick.next!=None:
            quick=quick.next.next
            slow=slow.next
            if quick==slow:
                quick=pHead
                while slow!=quick:
                    quick=quick.next
                    slow=slow.next
                return slow
        return None

使用数组来保存遍历过的节点，当遇到和先前节点一样的节点，那就是存在环，以及当前节点为环的入口。空间复杂度O(n) 时间复杂度O(n)

class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if pHead==None:
            return None
        l=pHead
        listnode=[]
        while l!=None:
            if l in listnode:
                return l
            listnode.append(l)
            l=l.next
        return None