首頁常見問題正文

單向鏈表長度未知,如何判斷其中是否有環(huán)?

更新時(shí)間:2024-02-02 來源:黑馬程序員 瀏覽量:

IT培訓(xùn)班

  判斷單向鏈表中是否存在環(huán)可以使用快慢指針的方法。這種方法非常有效,而且只需要常數(shù)的額外空間。以下是詳細(xì)的說明:

  1.快慢指針初始化:

  初始化兩個指針,一個稱為快指針(fast),另一個稱為慢指針(slow),初始時(shí)都指向鏈表的頭部。

  2.移動指針:

  快指針每次向前移動兩步,慢指針每次向前移動一步。

1706840930388_單向鏈表長度未知怎么判斷其中是否有環(huán).jpg

  3.檢測環(huán):

  如果存在環(huán),快指針最終會追上慢指針,形成一個循環(huán)。如果沒有環(huán),快指針將會先到達(dá)鏈表的末尾。

  下面是算法的具體步驟:

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

    # 如果快指針到達(dá)鏈表末尾,說明沒有環(huán)
    return False

  這個算法的關(guān)鍵在于快指針每次走兩步,而慢指針每次走一步。如果存在環(huán),快指針最終會在某一時(shí)刻與慢指針相遇。如果沒有環(huán),快指針會先到達(dá)鏈表的末尾。

  這個方法的時(shí)間復(fù)雜度是O(N),其中N是鏈表的長度,因?yàn)樵谧顗那闆r下,快指針需要遍歷整個鏈表。空間復(fù)雜度是 O(1),因?yàn)橹皇褂昧藘蓚€指針。

分享到:
在線咨詢 我要報(bào)名
和我們在線交談!