【leetcode刷題】16.環形連結清單——Java版

Question

141. 環形連結清單

難度：簡單

給定一個連結清單，判斷連結清單中是否有環。

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

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

進階：

你能用 O(1)（即，常量）記憶體解決此問題嗎？

示例 1：

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

輸出：true

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

示例 2：

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

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

示例 3：

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

輸出：false

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

提示：

連結清單中節點的數目範圍是 [0, 104]

-105 <= Node.val <= 105

pos 為 -1 或者連結清單中的一個 有效索引 。

Solution

雙指針法我們已經做過很多題，其中有一道移動零不知道大家還記得嗎？

快慢指針, 快指針每次比慢多走一個, 如果追上慢指針說明有環。

還有一個問題就是如何确定邊界值：

如果是環形連結清單，快慢指針就一定會有相遇的時候

如果不是環形連結清單，快慢指針的next就一定會有為空的時候。

這樣，無論是否是環形連結清單，都可以跳出循環。

Code

所有leetcode代碼已同步至github

歡迎star

/**
 * @author yitiaoIT
 */
 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;
    }
}      

Result

複雜度分析

• 時間複雜度：O(N)

🌈尋寶

⭐今天是堅持刷題更文的第16/100天

⭐各位的點贊、關注、收藏、評論、訂閱就是一條創作的最大動力

⭐更多算法題歡迎關注專欄《leetcode》

為了回饋各位粉絲，禮尚往來，給大家準備了一條多年積累下來的優質資源，包括 學習視訊、面試資料、珍藏電子書等

怎麼領取請大家自己找，尋寶遊戲現在開始。

找不到可以評論留言，一條就會注意到你。

如果還不行，請私信我。