最近在刷leetcode熟悉一些常用的算法知識齿桃，刷完了Two Pointers的大部分easy, medium 的題目洲押，在這里做一些總結(jié)，一來方便自己以后可以回看路操，又可以與大家分享自己的一點小小的心得疾渴。筆者用的語言是python千贯， 作為解釋性語言屯仗，對于追求效率的新手來說，非常適合入門（來自西南某高校的我第一門接觸到語言）搔谴，閑話不多說魁袜，我們開始走進Two pointers的套路。
Linked List Cycle（141敦第，142）
題目的大概意思是：
141:一個鏈表有沒有一個“環(huán)”(easy)
142:這個環(huán)的起點是哪個節(jié)點(medium)
對于是否是環(huán)峰弹，我們運用常用的 slow_pointer 和 fast_pointer 可以在O(N)復雜度下解決該問題：
解決方案的主體是一個循環(huán)，slow_pointet的速度為1芜果，fast_pointer的速度為2鞠呈， 如果存在“環(huán)” ，這兩個pointer總會在某一點相遇右钾；如果不存在“環(huán)”蚁吝，fast_pointer就會因為到達鏈表的尾部而跳出循環(huán)。
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
下一個問題就是如何找到環(huán)起點的位置舀射。我的思路很直接窘茁，也就是延續(xù)上一問題，首先改動原代碼如下：
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
此時脆烟，我們先找到環(huán)的大小山林，思路是當環(huán)內(nèi)一個pointer以1的速度移動，當返回到起點的時候邢羔，就知道了環(huán)的大小
因此我們新增一個tmp的pointer從head.next開始：
tmp, fast= head.next, fast.next
while not(fast is slow): tmp, fast= tmp.next, fast.next
此時head與tmp的距離也就是環(huán)的大小驼抹， 下面head與tmp同時以1的速度移動桑孩，當tmp與head重合的時候，這個重合點也就是環(huán)的起點框冀。
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
未完待續(xù)......
