Python 鏈表面試題精講：如何判斷鏈表是否有環(huán)？如何找出環(huán)的入口節(jié)點(diǎn)？
作者：Ss肥魚(yú)
今天我們就來(lái)剖析一道經(jīng)典題目：如何判斷一個(gè)鏈表是否有環(huán)？ 如果你掌握了這一技巧，那下一步你應(yīng)該深入學(xué)習(xí)：如何找到環(huán)的入口節(jié)點(diǎn)？
在 Python 面試中，鏈表的基礎(chǔ)題型幾乎每次都出現(xiàn)。今天我們就來(lái)剖析一道經(jīng)典題目：如何判斷一個(gè)鏈表是否有環(huán)？ 如果你掌握了這一技巧，那下一步你應(yīng)該深入學(xué)習(xí)：如何找到環(huán)的入口節(jié)點(diǎn)？
問(wèn)題描述
給定一個(gè)單向鏈表的頭節(jié)點(diǎn) head，判斷鏈表中是否存在環(huán)，如果存在，請(qǐng)返回環(huán)的起始節(jié)點(diǎn)。
解法一：判斷鏈表是否有環(huán)（快慢指針）
首先我們使用**快慢指針（Floyd 判圈算法）**來(lái)判斷鏈表是否有環(huán)：
- slow 每次走一步
- fast 每次走兩步
- 如果兩者在某個(gè)節(jié)點(diǎn)相遇，就說(shuō)明存在環(huán)
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解法二：找出環(huán)的入口（重點(diǎn)）
當(dāng)快慢指針相遇之后，說(shuō)明鏈表中存在環(huán)。此時(shí)我們可以使用如下方法找出環(huán)的起點(diǎn)（入口）：
步驟解析：
- 讓其中一個(gè)指針（如 slow）回到鏈表頭 head；
- 然后兩個(gè)指針都改為每次走一步；
- 當(dāng)兩個(gè)指針再次相遇時(shí)，就是環(huán)的入口。
原理解釋：
設(shè)：
- a 是頭節(jié)點(diǎn)到環(huán)入口的長(zhǎng)度；
- b 是環(huán)入口到相遇點(diǎn)的長(zhǎng)度；
- c 是環(huán)剩下的長(zhǎng)度（使得一圈為 b + c）；
因?yàn)榭熘羔樧叩木嚯x是慢指針的兩倍：
2(a + b) = a + b + n(b + c)
推導(dǎo)得：a = c + (n - 1)(b + c)說(shuō)明從頭節(jié)點(diǎn)走 a 步、從相遇點(diǎn)走 c 步，兩者會(huì)在環(huán)的入口節(jié)點(diǎn)重合。
完整代碼實(shí)現(xiàn)
class ListNode:
def __init__(self, val=0):
self.val = val
self.next = None
def detect_cycle(head: ListNode) -> ListNode:
"""
檢測(cè)鏈表中的環(huán)，返回環(huán)的起始節(jié)點(diǎn)。如果無(wú)環(huán)返回 None。
"""
slow = fast = head
# 第一步：判斷是否有環(huán)
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None # 無(wú)環(huán)
# 第二步：找環(huán)的入口
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow # 即為環(huán)的起始節(jié)點(diǎn)測(cè)試樣例
# 創(chuàng)建一個(gè)環(huán)形鏈表：1 -> 2 -> 3 -> 4 -> 5 -> 3（回到節(jié)點(diǎn)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 # 形成環(huán)，入口是node3
entry = detect_cycle(node1)
print(entry.val if entry else "無(wú)環(huán)") # 輸出：3小結(jié)與面試建議
面試點(diǎn) | 內(nèi)容說(shuō)明 |
判斷有無(wú)環(huán) | 快慢指針，相遇則有環(huán) |
找到環(huán)入口 | 相遇后讓一指針回頭，兩個(gè)再同步前進(jìn) |
時(shí)間復(fù)雜度 | O(n) |
空間復(fù)雜度 | O(1) |
這道題常被用于考察鏈表的操作能力、指針?biāo)季S和空間復(fù)雜度控制能力，理解 Floyd 判圈算法對(duì)于高級(jí)題型也是非常有幫助的。
責(zé)任編輯：趙寧寧
來(lái)源：
Ssoul肥魚(yú)
