【Leetcode 筆記】141. Linked List Cycle

題目解釋

給定 linked list 的 head，判斷 linked list 中是否有 cycle。
如果有則傳回 true。否則，傳回 false。

範例

• 輸入: head = [3, 2, 0, -4], pos = 1
• 輸出: True

linked list 中有一個 cycle，尾部會連接到第一個節點（0-index）。

最佳解法

又又又來到了我們的 快慢指針法（Fast-slow Pointers） 出場的時間。

快慢指針法（Fast-slow Pointers）

標準題中的標準題。

假設一個 linked list 沒有 cycle，
那前進不同步數的 slow 跟 fast 這輩子都不可能會相交 ❌

但是如果 linked list 有 cycle，
slow 跟 fast 跑了一段時間後，一定會在一個 node 上相交 ✅

就好像如果想要認識一個人，
那就觀察他的朋友們，成為他的朋友的朋友，
完成一個 cycle 後，你們總會在哪相遇的（奇怪的比喻 ？）

不多說了，上 code！

程式碼

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        dummy = ListNode(0, head)
        slow, fast = dummy, dummy

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                return True

        return False

時間複雜度

O(n)，n 是 linked list 的元素個數。

空間複雜度

O(1)，沒有多存東西。

結語

因為我是按照 Neetcode 的 Blind 75 刷下來的，
我總覺得這題好像才是快慢指針的入門題 😅

還有我強烈懷疑，
這個說了又不傳到 func 的 pos 是來有效干擾人的❓

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26