️LeetCode每日一題️

---

• 博客主頁：南七的博客主頁
• 期待得到大家的點贊收藏留言和關注
• 持續刷題，每日一題 05
• Leetcode 熱題 Hot100
• 博主水平有限，如果發現有不對的地方，希望大佬們指正！
• 放弃很容易,但堅持一定很酷,人生一次,怎願甘拜下風！
• 來源：Leetcode 熱題 Hot100 141. 環形鏈錶
• 系列文章持續更新中…
       1.擋住眾人的兩數之和…
      2.趁室友吃雞，刷一道回文鏈錶
       3.我連兩個數相加都不會（撓頭ing）（Leetcode 熱題 Hot100）
       4.終於秒殺了一題【删除鏈錶的倒數第 N 個結點】（Leetcode 熱題 Hot100）
  
  

---

題目描述
給你一個鏈錶的頭節點 head ，判斷鏈錶中是否有環。
如果鏈錶中有某個節點，可以通過連續跟踪 next 指針再次到達，則鏈錶中存在環。 為了錶示給定鏈錶中的環，評測系統內部使用整數 pos 來錶示鏈錶尾連接到鏈錶中的比特置（索引從 0 開始）。如果 pos 是 -1，則在該鏈錶中沒有環。注意：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️⃣:


剛拿到題目還是有點懵的，沒看懂題目的pos是什麼意思。之後才反應過來，pos標明的是鏈錶尾所指向前面結點的索引號。該題要求判斷鏈錶是否成環，該鏈錶是單向鏈錶，那麼應該就會想到，如果鏈錶成環的話，其中的某些結點一定是會被重複訪問的。那麼第一個想到的就是，我們只要知道，該鏈錶是否被訪問過就可以了。可惜不是自定義的鏈錶結構，我第一個想到的是給每一個結點添加一個狀態，被訪問過的結點直接更改其狀態就可以了。可是，鏈錶結構是規定死的，無法更改。這就突然讓我想到使用哈希錶的辦法。對於每一個訪問過的結點，我們只需要將其添加到哈希錶中即可。那麼Set集合就可以很好的幫助我們，set集合是不允許出現重複元素的，當我們想要向錶中添加已經存在的元素時，就會返回false，那麼這個就是我們的關鍵判斷條件了。

public class Solution {
    
    public boolean hasCycle(ListNode head) {
    
        Set<ListNode> set = new HashSet<>();
        ListNode cur = head;
        while(cur != null){
    
        	//如果當前結點已經遍曆過了，就添加失敗，返回false
            if(!set.add(cur)){
    
                return true;
            }
            //指針後移
            cur = cur.next;
        }
        return false;
    }
}

博主題解2️⃣:


還有一種辦法–快慢指針。我們給定兩個指針，讓他們都指向頭結點，快指針每次向後遍曆兩個結點，慢指針每次向後遍曆一個結點。試想一下，如果鏈錶成環，那麼快指針很快又會和慢指針相遇。這就像我們在一個操場上跑步，你們同時出發，可能下次再見到他的時候，他已經甩你一圈了。所以，我們只需要判斷，兩個指針是否相遇，如果相遇，就說明鏈錶成環。如果fast指針為空了，就說明鏈錶不成環。

public class Solution {
    
    public boolean hasCycle(ListNode head) {
    
        if(head == null){
    
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        //這裏只需要判斷快指針就行了
        //博主一開始還傻乎乎的在那判斷slow != null，快指針為null，自然就不需要判斷慢指針了
        while(fast != null&&fast.next != null){
    
        	//快指針每次向後遍曆兩個結點
            fast = fast.next.next;
            //慢指針每次向後遍曆一個結點
            slow = slow.next;
			//如果二者相遇，說明鏈錶成環，返回true
            if(fast == slow)
                return true;
        }
        return false;

    }
}

期待得到大家的點贊收藏留言和關注