【日拱一卒】鏈表——判斷鏈表是否有環(huán)

需求

判定一個鏈表是否有環(huán)

0704-1-不存在環(huán).png

這張圖不存在環(huán)魂毁，頭結點是1荚藻，尾結點是5。

0704-2-存在環(huán).png

這張圖中啥刻，節(jié)點2-3-4-5-2就構成了環(huán)秃殉。

思路

思路1 ——快慢指針

顧名思義坝初，一個快指針，一個慢指針钾军。

如果不包括環(huán)鳄袍，快慢指針同向行駛，根據小學經典數學題巧颈，他們永遠無法相遇畦木，而且差距只會越來越大。

如果鏈表有環(huán)砸泛，意味著快慢指針都會調頭十籍，好比操場跑步，第一圈快指針在慢指針前面唇礁，但是后面快指針遲早會追上慢指針勾栗。所以可以借助這個思想，使用快慢指針判定是否有環(huán)盏筐。

0704-3-快慢指針.png

圖中围俘，slow代表慢指針，每次只走一步琢融，fast代表快指針界牡，每次走兩步。

第一次：slow停在節(jié)點2漾抬，fast停在節(jié)點3

第二次：slow停在節(jié)點3宿亡，fast停在節(jié)點5

第三次：slow停在節(jié)點4，fast停在節(jié)點3

第四次：slow停在節(jié)點5纳令，fas停在節(jié)點5

至此挽荠，快指針已經”攆上“了慢指針克胳。

代碼實現

func hasCycle(head *ListNode) bool {
    slow := head
    fast := head

    for fast.Next != nil && fast != nil {
        if slow.Val == fast.Val {
            return true
        } else {
            slow = slow.Next
            fast = fast.Next.Next
        }
    }

    return false
}

思路2——另辟蹊徑

遍歷鏈表，如果節(jié)點的值與一個特殊的值不相等圈匆，則將遍歷過的節(jié)點的值設置成一個特殊的值漠另，相當于打標記。

如果鏈表遍歷完跃赚，發(fā)現所有節(jié)點都不等于這個特殊的值笆搓，則判定鏈表無環(huán)。

如果在遍歷的過程中来累，發(fā)現有節(jié)點等于這個特殊的值砚作，則認為有環(huán)。

代碼實現

func hasCycle2(head *ListNode02) bool {
    if head == nil {
        return false
    }

    for head != nil {
        if head.Val == 5201314 {
            return true
        }

        head.Val = 5201314
        head = head.Next
    }

    return false
}

只能說嘹锁，第一個想到這個思路的，腦洞是有多大~

不忘初心

老王：你不好好種地着裹，你以后長大能干什么

小王：學算法

老王：學算法领猾？！你數組骇扇、鏈表摔竿、棧、隊列少孝、堆继低、排序、查找都整不明白稍走，你學什么算法

小王：我只學如何判斷鏈表是否有環(huán)

老王：袁翁。。婿脸。

?著作權歸作者所有,轉載或內容合作請聯系作者