Программисты сравнили эффективность алгоритмов Java и Python для обнаружения циклов в списках

DAY 8 自我挑戰組 30天 LeetCode 演算法實戰：Java 與 Python 解法比較 系列 第 8 篇 Day 08｜Linked List Cycle：Java 與 Python 實作 Fast & Slow Pointers 一、題目介紹 本題為LeetCode的Linked List Cycle 給定一個Linked List，需要判斷其中是否存在一個 循環（Cycle） 正常的Linked List最後會指向 null ：1 → 2 → 3 → 4 → null 但如果某個節點的 next 又指向前面的節點，就會形成循環 此時Linked List就不會走到 null ，而是會一直在循環中移動 因此需要判斷 有 Cycle → true 沒有 Cycle → false 二、解題思路 本題可以使用非常經典的 Fast & Slow Pointers（快慢指標） ，也稱為 Floyd's Cycle Detection Algorithm 建立兩個指標 slow → 一次移動 1 個節點 fast → 一次移動 2 個節點 如果Linked List 沒有循環 1 → 2 → 3 → 4 → null fast 最終會先抵達 null ，因此可以判斷沒有Cycle 如果Linked List 存在循環 由於 fast 比 slow 快，再循環中移動時，兩個指標最終一定會相遇 因此 fast 遇到 null → 沒有 Cycle fast 與 slow 相遇 → 有 Cycle 三、解題流程 假設Linked List為 1 → 2 → 3 → 4 → 2... 其中 4 又指向 2 ，因此形成循環 一開始 slow = 1 fast = 1 第一次移動 slow → 2 fast → 3 第二次 slow → 3 fast → 2 第三次 slow → 4 fast → 4 兩個指標相遇 slow == fast 因此可以判斷 true 為什麼一定會相遇？ 這是Fast & Slow Pointers很重要的觀念。 如果存在循環，slow和fast都會進入同一個循環。 假設： slow 每次前進 1 fast 每次前進 2 那麼fast每一次相對於slow都會多前進1個節點。 因為循環是有限長度，所以fast最終一定會追上slow。 就像兩個人在圓形跑道上跑步，一個速度比較快，只要一直跑，就一定會在某個位置追上另一個人。 四、Java實作 五、Python實作 六、時間與空間複雜度 Java Time Complexity：O(n) slow 與 fast 都會沿著 Linked List 移動。 在沒有Cycle的情況下， fast 會走到結尾。 在有Cycle的情況下，兩個指標會在有限次移動後相遇。 Space Complexity：O(1) 只使用 slow 與 fast 兩個指標。 不需要建立額外的HashSet或其他資料結構。 Python Time Complexity：O(n) 使用快慢指標走訪Linked List。 Space Complexity：O(1) 只使用兩個指標變數。 不需要額外儲存每個節點。 七、Java與Python解法比較 快慢指標 Java： slow = slow.next; fast = fast.next.next; Python： slow = slow.next fast = fast.next.next 兩種語言的邏輯完全相同。 slow 每次移動一格，而 fast 每次移動兩格。 判斷指標是否相遇 Java：if (slow == fast) Python：if slow == fast: 這裡比較的是 節點本身是否為同一個節點 ，而不是比較節點中的val。 這點非常重要。 例如兩個不同節點都可能存放：val = 3 但它們仍然是不同的節點。 因此需要判斷的是：slow == fast 而不是：slow.val == fast.val 判斷是否到達結尾 Java：fast!= null && fast.next!= null Python：fast and fast.next Python可以利用 None 的判斷方式，讓程式碼更加簡潔。 複雜度比較 兩種語言使用相同的Fast & Slow Pointers演算法，因此複雜度相同。 八、實作結果 LeetCode 測試結果：Accepted 九、今日學習心得 今天學習了 Fast & Slow Pointers（快慢指標） ，並利用這個技巧判斷Linked List 是否存在循環。 如果使用一般的方法，可以將已經走訪過的節點存入HashSet，當再次遇到相同節點時，就可以判斷存在Cycle。不過這種方法需要額外的記憶體，因此空間複雜度為O(n)。 今天使用的Fast & Slow Pointers則不需要儲存所有節點，只需要兩個指標，就可以透過移動速度的差異判斷兩個指標是否會相遇，因此可以將額外空間降低到O(1)。 透過今天的練習，我了解到有些問題不一定需要記錄「所有走過的資料」，也可以透過指標之間的移動關係來得到答案。 今天的核心觀念：Slow 一步、Fast 兩步；遇到 null 沒循環，兩者相遇就是有循環。 系列文 30天 LeetCode 演算法實戰：Java 與 Python 解法比較 共 12 篇 目錄 8 Day 08｜Linked List Cycle：Java 與 Python 實作 Fast & Slow Pointers 9 Day 09｜Maximum Depth of Binary Tree：Java 與 Python 實作 DFS 10 Day 10｜Invert Binary Tree：Java 與 Python 實作 Binary Tree 11 Day 11｜Binary Tree Inorder Traversal：Java 與 Python 實作 Tree Traversal 12 Day 12｜Binary Tree Level Order Traversal：Java 與 Python 實作 BFS 完整目錄 尚未有邦友留言 立即登入留言