更新時間:2024-02-02 來源:黑馬程序員 瀏覽量:
IT就到黑馬程序員.gif)
判斷單向鏈表中是否存在環(huán)可以使用快慢指針的方法。這種方法非常有效,而且只需要常數(shù)的額外空間。以下是詳細的說明:
初始化兩個指針,一個稱為快指針(fast),另一個稱為慢指針(slow),初始時都指向鏈表的頭部。
  快指針每次向前移動兩步,慢指針每次向前移動一步。
.jpg)
如果存在環(huán),快指針最終會追上慢指針,形成一個循環(huán)。如果沒有環(huán),快指針將會先到達鏈表的末尾。
  下面是算法的具體步驟:
class ListNode: def __init__(self, value): self.value = value self.next = None def has_cycle(head): # 初始化快慢指針 slow = head fast = head # 遍歷鏈表 while fast is not None and fast.next is not None: # 移動慢指針一步 slow = slow.next # 移動快指針兩步 fast = fast.next.next # 檢測是否相遇,即是否存在環(huán) if slow == fast: return True # 如果快指針到達鏈表末尾,說明沒有環(huán) return False
這個算法的關(guān)鍵在于快指針每次走兩步,而慢指針每次走一步。如果存在環(huán),快指針最終會在某一時刻與慢指針相遇。如果沒有環(huán),快指針會先到達鏈表的末尾。
這個方法的時間復(fù)雜度是O(N),其中N是鏈表的長度,因為在最壞情況下,快指針需要遍歷整個鏈表??臻g復(fù)雜度是 O(1),因為只使用了兩個指針。
1024首播|39歲程序員逆襲記:不被年齡定義,AI浪潮里再迎春天
2025-10-241024程序員節(jié)丨10年同行,致敬用代碼改變世界的你
2025-10-24【AI設(shè)計】北京143期畢業(yè)僅36天,全員拿下高薪offer!黑馬AI設(shè)計連續(xù)6期100%高薪就業(yè)
2025-09-19【跨境電商運營】深圳跨境電商運營畢業(yè)22個工作日,就業(yè)率91%+,最高薪資達13500元
2025-09-19【AI運維】鄭州運維1期就業(yè)班,畢業(yè)14個工作日,班級93%同學(xué)已拿到Offer, 一線均薪資 1W+
2025-09-19【AI鴻蒙開發(fā)】上海校區(qū)AI鴻蒙開發(fā)4期5期,距離畢業(yè)21天,就業(yè)率91%,平均薪資14046元
2025-09-19