python双指针算法，解决环形链表的判断问题

对于判断一个链表是不是存在环这个问题，其实是一个较为经典的问题，无论是直接还是间接，经常都会遇到。而对于解决这个问题的方法也多种多样，这里主要是提供了一种使用快慢双指针算法来进行这个问题的解决。

对于给定的一个链表，需要判断这个链表中是否有环，例如给定一个链表head=[3,2,0,-4]，使用一个变量来代表链尾连接到链表中的位置，pos=1，这个就代表这个链表中存在环，并且这个链表的尾部是连接到了给定数据列表中的第二个数据，如下图所示，判断存在环的输出即为true。

添加图片注释，不超过 140 字（可选）

再如给定的链表是head=[1,2]，给定的pos是1，同样也是存在环的，如下图所示，环存在于尾部连接到第一个数据之间，返回的结果也是true。

添加图片注释，不超过 140 字（可选）

而对于给定的链表是head=[1]，pos=-1的时候，不存在环，返回的结果是false，如下图所示。

添加图片注释，不超过 140 字（可选）

针对这个问题，首先是如果一个链表内部形成了环，假设两个速度相同的物体从同一个位置开始出发的话，那在环上经过的物体和不在环上经过的物体所使用的时间肯定是不一样的，所以这里就相当于存在一个追逐的关系，两者所花的时间不一样，但是终点是一样的，最终两者都会在终点相遇，但是移动速度快的一方怎么都会追上移动速度慢的一方，这也就是该问题的一个阶梯思路，需要定义两个指针从链表的头部开始遍历。

定义一个循环，这个循环的条件是只要快指针所指向的节点存在那就进入到循环中，而当快指针遍历到最后的尾节点，即快指针指向的节点的next下一个节点是空的时候，即终止循环，同时也就表示这个链表中是不存在环的。

而当快指针每移动两步，慢指针每次移动一步的时候，如果两者会相遇，那就表示了这个链表中使存在环的，也返回输出。python代码实现如下：

class ListNode(object):#链表中节点类
    def __init__(self, x):
        self.val = x
        self.next = None
#判断是否有环函数Cycle
def Cycle(self, head):
    if head==None:return False
    fast=head
    slow=head
    while(fast):
        if fast.next==None:
            return False
        fast=fast.next.next
        slow=slow.next
        if fast==slow:
            return True
    return False

针对使用快慢指针的方式，如果假设定义链表的长度是n，如果链表中不存在环，那遍历整个链表的节点就是时间复杂度也就是O(n)，空间复杂度只为O(1)。但是如果链表中是存在环的，思路分析所经过的节点其实是快指针经过的环形节点和慢指针所遍历的所有节点，应该是两个经过的节点之和，时间复杂度仍是O(n),空间复杂度仍是O(1)，所以这个方法是较为高效的。