鏈表有環知多少~
大家好，我是程式設計師學長。
今天我們來聊一聊面試中經常考的一道題目，判斷鏈表是否有環。
如果喜歡，記得點個關注呀~
問題描述
給定一個鏈表，判斷鏈表中是否有環。如果鏈表中有某個節點，可以通過連續跟蹤 next 指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環。注意：pos 不作為參數進行傳遞，僅僅是為了標識鏈表的實際情況。
如果鏈表中存在環，則返回 true 。 否則，返回 false 。
示例：
輸入：head = [-1,-7, 7,-4, 9, 6, -5, -2], pos = 3
輸出：true
解釋：鏈表中有一個環，其尾部連接到第二個節點。
分析問題
拿到這個問題，我們最直觀的想法就是在遍歷結點的過程中去標記一下這個結點是否已經被訪問過。如果被訪問過，那麼就代表該鏈表有環，直接返回。如果沒有被訪問過，我們就標記一下，然後接著去遍歷下一個結點，直到遍歷完整個鏈表為止。下面我們來看一下程式碼的實現。
def hasCycle(self, head):
tags = set()
while head:
#表示已經被訪問過了，代表有環
if head in tags:
return True
tags.add(head)
head = head.next
return False
我們可以知道該演算法的時間複雜度和空間複雜度都是O(n)。那我們有更好的解法嗎？
優化
你可以這麼思考，當有兩名同學在操場上以不同的速度進行跑步，它們最終肯定會相遇。因為操場是環形的，如果在直線上跑，那他們肯定不會相遇。
我們假設同學1以速度1在跑，同學2以速度2在跑。
下面我們來看一下程式碼如何實現。
def hasCycle(self, head):
#如果鏈表為空或者鏈表只有一個結點
#直接返回false,因為不可能有環
if not head or not head.next:
return False
#快慢指針
slow = fast = head
start = True
while slow != fast || start:
start=False
if not fast or not fast.next:
return False
slow = slow.next
fast = fast.next.next
return True
我們這裡引入了一個變數start表示是否是起跑。
可以看到該演算法的空間複雜度降低為O(1)。
最後
到此為止，我們就把這道題聊完了。
原創不易，各位覺得文章不錯的話，不妨點贊、在看、轉發三連走起！
你知道的越多，你的思維也就越開闊，我們下期再見。
