leetcode算法141.環形連結清單

哈喽！大家好，我是【學無止境小奇】，一位熱愛分享各種技術的部落客！

⭐【學無止境小奇】的創作宗旨：每一條指令都親自執行過，每一行代碼都實際運作過，每一種方法都真實實踐過，每一篇文章都良心制作過。✊✊✊

⭐【學無止境小奇】的部落格中所有涉及指令、代碼的地方，除了提供圖檔供大家參考，另外會在圖檔下方提供一份純文字格式的指令或者代碼友善大家粘貼複制直接執行指令或者運作代碼。

⭐如果你對技術有着濃厚的興趣，歡迎關注【學無止境小奇】，歡迎大家和我一起交流。

❤️❤️❤️感謝各位朋友接下來的閱讀❤️❤️❤️

文章目錄

• ​​一、leetcode算法​​

• ​​ 1、環形連結清單​​

• ​​1.1、題目​​
• ​​1.2、思路​​
• ​​1.3、答案​​

一、leetcode算法

1、環形連結清單

1.1、題目

給你一個連結清單的頭節點 head ，判斷連結清單中是否有環。

如果連結清單中有某個節點，可以通過連續跟蹤 next 指針再次到達，則連結清單中存在環。 為了表示給定連結清單中的環，評測系統内部使用整數 pos 來表示連結清單尾連接配接到連結清單中的位置（索引從 0 開始）。注意：pos 不作為參數進行傳遞 。僅僅是為了辨別連結清單的實際情況。

如果連結清單中存在環 ，則傳回 true 。 否則，傳回 false 。

示例 1：

輸入：head = [3,2,0,-4], pos = 1

輸出：true

解釋：連結清單中有一個環，其尾部連接配接到第二個節點。

示例 2：

輸入：head = [1,2], pos = 0

輸出：true

解釋：連結清單中有一個環，其尾部連接配接到第一個節點。

示例 3：

輸入：head = [1], pos = -1

輸出：false

解釋：連結清單中沒有環。

1.2、思路

思路一：此題可以用哈希表來解決，将每一個節點都放入哈希表中，如果有節點重複就證明有環，這種算法的空間複雜度為O(n)，即最壞的情況将所有的節點都放入哈希表中。

思路二：可以用快慢指針來解決，定義一個快指針，一個慢指針，快指針每次走兩步，慢指針每次走一步，如果沒有環，那麼快指針會走到頭結束，如果有環，快指針會在環中一直循環，等到慢指針也進入環中循環，然後他們會在環中相遇，這就證明有環，這種算法空間複雜度為O(1)。

1.3、答案

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while(slow != fast){
            if(fast == null || fast.next ==null){
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}      

複雜度分析

時間複雜度：O(N)，其中 N 是連結清單中的節點數。

當連結清單中不存在環時，快指針将先于慢指針到達連結清單尾部，連結清單中每個節點至多被通路兩次。

當連結清單中存在環時，每一輪移動後，快慢指針的距離将減小一。而初始距離為環的長度，是以至多移動 N 輪。