個人主頁：白日依山璟
專欄：Java|數據結構與算法|每日一題
文章目錄
- 1. 題目描述
- 示例1：
- 示例2：
- 示例3：
- 提示:
- 2. 思路
- 3. 代碼
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
解釋：鏈表中沒有環。
提示:
- 鏈表中節點的數目范圍是
[0, 104] -105 <= Node.val <= 105pos為-1或者鏈表中的一個有效索引 。
題目鏈接
2. 思路
- 定義兩個指針，一快一慢。慢指針每次移動一次，而快指針每次移動兩步。
- 初始化時，位置都在
head - 循環遍歷鏈表，移動快慢指針，如果在移動的過程中，快指針反過來追上慢指針，就說明該鏈表為環形鏈表。否則快指針到達鏈表尾部，該鏈表不為環形鏈表。
動畫：
3. 代碼
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) {return true;}}return false;}
}
運行結果：
世界上有三種k，梅花k，方片k，還有任何人不關注我我都會難過的ok
)
