最近在刷leetcode熟悉一些常用的算法知识，刷完了Two Pointers的大部分easy, medium 的题目，在这里做一些总结，一来方便自己以后可以回看，又可以与大家分享自己的一点小小的心得。笔者用的语言是python， 作为解释性语言，对于追求效率的新手来说，非常适合入门（来自西南某高校的我第一门接触到语言），闲话不多说，我们开始走进Two pointers的套路。

Linked List Cycle（141，142）

题目的大概意思是：
141:一个链表有没有一个“环”(easy)
142:这个环的起点是哪个节点(medium)

对于是否是环，我们运用常用的 slow_pointer 和 fast_pointer 可以在O(N)复杂度下解决该问题：
解决方案的主体是一个循环，slow_pointet的速度为1，fast_pointer的速度为2， 如果存在“环” ，这两个pointer总会在某一点相遇；如果不存在“环”，fast_pointer就会因为到达链表的尾部而跳出循环。

def hasCycle(self, head):
    """
    :type head: ListNode
    :rtype: bool
    """
    if head is None : return False
    slow, fast = head, head
    while True:
        if fast.next == None: return False
        if fast.next.next == None: return False
        slow, fast = slow.next, fast.next.next
        if slow is fast: return True

下一个问题就是如何找到环起点的位置。我的思路很直接，也就是延续上一问题，首先改动原代码如下：

    if head is None: return None
    slow, fast = head, head
    while True:
        if fast.next == None: return None
        if fast.next.next == None: return None
        slow, fast = slow.next, fast.next.next
        if slow is fast: break

此时，我们先找到环的大小，思路是当环内一个pointer以1的速度移动，当返回到起点的时候，就知道了环的大小
因此我们新增一个tmp的pointer从head.next开始：

    tmp, fast= head.next, fast.next
    while not(fast is slow): tmp, fast= tmp.next, fast.next

此时head与tmp的距离也就是环的大小， 下面head与tmp同时以1的速度移动，当tmp与head重合的时候，这个重合点也就是环的起点。

    while not(head is tmp): tmp, head= tmp.next, head.next

因此完整的代码是：

def detectCycle(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    if head is None: return None
    slow, fast = head, head
    while True:
        if fast.next == None: return None
        if fast.next.next == None: return None
        slow, fast = slow.next, fast.next.next
        if slow is fast: break
    
    tmp, fast= head.next, fast.next
    while not(fast is slow): tmp, fast= tmp.next, fast.next
    while not(head is tmp): tmp, head= tmp.next, head.next
    return head

未完待续......