Leetcode之旅|判斷鏈表是否存在環

　　今天記錄的是兩道特別有意思的題：判斷鏈表中存不存在環(circle)。為了找解法，在紙上畫了各種數字、箭頭、圈圈和推導，還以為在研究什麼彩票號碼呢哈哈 ~ ~ ~

題目描述

　　和昨天一樣，今天的兩道題同樣是分為基礎版和進階版，不同的是，今天的兩個版本可以看作是一道大題的兩小問，二者關聯性更強。

　　基礎版：

　　

　　　　判斷鏈表是否存在環。(141. Linked list cycle)

　

　　進階版：

　　

　　　　若存在環，找出環的起點。(142. Linked list cycle II)　　 　 　

　　另外，要求在不修改鏈表的同時，空間複雜度為 。

解題思路

基礎版

　　這道題我一開始是聯想到了之前學習DFS的思路，即遍歷每個節點，並在訪問後做上visited的標記，如果訪問到一個已經標記的節點，說明有環。然而想法是美好的，不，也並不美好，畢竟這個空間複雜度不是 ，而且發現沒那麼好實現，因為單向鏈表的特點就是不能回頭，你很容易知道一個節點的下一個節點是啥，但前一個節點是啥？不能直接知道。

　　後來逛了下別人的答案，感覺自己被羞辱了，思路完全不一樣啊！完全沒這麼想啊！看來還是經驗不夠啊！(受打擊三連)又學習到了。具體怎麼做呢？需要用到兩個指針，一個每次走一步(slow)，另一個走得快一點，每次走兩步(fast)，咳咳，重點來了 ~ 如果一個鏈表不存在環，那總會走向終點(遇到Null)；如果存在環呢？那兩個指針會一直走下去，但這樣循環沒法終止，就沒法返回結果，所以進一步的判斷依據是，如果存在環，slow和fast兩個指針會相遇，一旦相遇，循環終止，即可返回結果。代碼如下：

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

進階版

　　雖然有了基礎版的打底，但進階版也折騰了我很久，最後還是借了別人的智慧才解決的，唉，心塞。 和基礎版一樣，我們需要設置兩個指針，均初始化為head(如果有的話)，因為沒有環的情況很好判斷，我們接下來只討論在有環的情況下，如何找環的起始點。

　　將head看作第一個節點，那麼如果走 步的話，slow將會到達第 個節點，而fast會到達第 個節點。當二者第一次相遇(meet)，設在第 個節點，那麼slow和fast的距離為 個節點，那麼 一定是環的節點個數( )的整數倍，即：

這時候我們再設一個指針head，初始為第一個節點的位置(head),那麼此時slow(或者fast,因為循環終止條件是二者相同)與head的距離為 。此時再分兩種情況討論。

　　如果第一次相遇的點就是head，那麼說明head就是環的入口,直接返回head即可。這點很好理解。

　　

　　如果第一次相遇的不是head，,那麼讓head和slow以相同速度前進，當head到達環的入口時，因為slow和head的距離為 ，那麼二者必然相遇。 因為對於head而言，之前沒有相遇的機會，所以第一次相遇的點必然是入口，返回head即可。

　　代碼如下：

def detectCycle(head): """ :type head: ListNode :rtype: ListNode """ if not head: return None slow, fast = head, head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: break if not fast or not fast.next: return None if head == slow: return head _head = head while _head != slow: _head = _head.next slow = slow.next return _head

總結

　　刷完鏈表就刷樹和圖吧，數據結構太有意思了。記得之前我關注的一個博主曾在合理使用堆棧給出某道題很elegant的解法時感慨：「啊，這就是數據結構的勝利！！！」而我目前還只是在練習一些很簡單的操作，希望我以後也能將它們變為趁手的利刃吧。

轉載自個人博客

Leetcode之旅|鏈表啊，鏈表! (2)www.quanlion.com
推薦閱讀：