題目
#

leetcode 141 - Linked List Cycle(題目說明請點連結)

題目簡述
#

判斷一個鏈表是否有環。

ＴExample 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: 鏈表中有環，尾節點連接到第1個節點（索引從0開始）。

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: 鏈表中有環，尾節點連接到第0個節點。

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: 鏈表中沒有環。

解題思路
#

這題確認 Linked List 是否有 Cycle ，回傳true、flase。
可以用上快慢指針確認是否有Cycle：
Linked List Cycle slow 一次走1個節點，fast 一次走2個節點，只要 fast 與 slow 相遇即是有Cycle。

初始情況：slow = head = 3，fast = head = 3

第一次迭代：
- slow = slow.next = 2
- fast = fast.next.next = 0
- slow = 2，fast = 0
第二次迭代：
- slow = slow.next = 0
- fast = fast.next.next = 2
- slow = 0，fast = 2
第三次迭代：
- slow = slow.next = -4
- fast = fast.next.next = 0
- slow = -4，fast = 0
第四次迭代：
- slow = slow.next = 2（回到節點2）
- fast = fast.next.next = 2（回到節點2）
- slow = 2，fast = 2
- slow == fast，返回 true

完整程式碼
#

java

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; // 無環
    }
}