Python 鏈表面試題精講：如何判斷鏈表是否有環？如何找出環的入口節點？
作者：Ss肥魚
今天我們就來剖析一道經典題目：如何判斷一個鏈表是否有環？ 如果你掌握了這一技巧，那下一步你應該深入學習：如何找到環的入口節點？
在 Python 面試中，鏈表的基礎題型幾乎每次都出現。今天我們就來剖析一道經典題目：如何判斷一個鏈表是否有環？ 如果你掌握了這一技巧，那下一步你應該深入學習：如何找到環的入口節點？
問題描述
給定一個單向鏈表的頭節點 head，判斷鏈表中是否存在環，如果存在，請返回環的起始節點。
解法一：判斷鏈表是否有環（快慢指針）
首先我們使用**快慢指針（Floyd 判圈算法）**來判斷鏈表是否有環：
- slow 每次走一步
- fast 每次走兩步
- 如果兩者在某個節點相遇，就說明存在環
def has_cycle(head: ListNode) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False解法二：找出環的入口（重點）
當快慢指針相遇之后，說明鏈表中存在環。此時我們可以使用如下方法找出環的起點（入口）：
步驟解析：
- 讓其中一個指針（如 slow）回到鏈表頭 head；
- 然后兩個指針都改為每次走一步；
- 當兩個指針再次相遇時，就是環的入口。
原理解釋：
設：
- a 是頭節點到環入口的長度；
- b 是環入口到相遇點的長度；
- c 是環剩下的長度（使得一圈為 b + c）；
因為快指針走的距離是慢指針的兩倍：
2(a + b) = a + b + n(b + c)
推導得：a = c + (n - 1)(b + c)說明從頭節點走 a 步、從相遇點走 c 步，兩者會在環的入口節點重合。
完整代碼實現
class ListNode:
def __init__(self, val=0):
self.val = val
self.next = None
def detect_cycle(head: ListNode) -> ListNode:
"""
檢測鏈表中的環，返回環的起始節點。如果無環返回 None。
"""
slow = fast = head
# 第一步：判斷是否有環
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None # 無環
# 第二步：找環的入口
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow # 即為環的起始節點測試樣例
# 創建一個環形鏈表：1 -> 2 -> 3 -> 4 -> 5 -> 3（回到節點3）
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node3 # 形成環，入口是node3
entry = detect_cycle(node1)
print(entry.val if entry else "無環") # 輸出：3小結與面試建議
面試點 | 內容說明 |
判斷有無環 | 快慢指針，相遇則有環 |
找到環入口 | 相遇后讓一指針回頭，兩個再同步前進 |
時間復雜度 | O(n) |
空間復雜度 | O(1) |
這道題常被用于考察鏈表的操作能力、指針思維和空間復雜度控制能力，理解 Floyd 判圈算法對于高級題型也是非常有幫助的。
責任編輯：趙寧寧
來源：
Ssoul肥魚
