題目說明

141. Linked List Cycle
     給定一個連結串列，判斷它是否有環（cycle）。
     若某個節點在連結串列中再次被訪問到，則表示存在環。

範例

Input: head = [3,2,0,-4], pos = 1
（代表尾節點指向 index = 1 的節點）
Output: true

Python 解法

解法 1：快慢指針（Floyd’s Cycle Detection）

class ListNode:
def init(self, x):
self.val = x
self.next = None
def hasCycle(head: ListNode) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False

解法 2：哈希集合（記錄節點）

def hasCycle(head: ListNode) -> bool:
visited = set()
while head:
if head in visited:
return True
visited.add(head)
head = head.next
return False

Java 解法

解法 1：快慢指針（Floyd’s Algorithm）

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

解法 2：HashSet 記錄節點

import java.util.HashSet;
public class Solution {
public boolean hasCycle(ListNode head) {
HashSet visited = new HashSet<>();
while (head != null) {
if (visited.contains(head)) {
return true;
}
visited.add(head);
head = head.next;
}
return false;
}
}

⏱️ 複雜度分析

• 快慢指針法：

  • 時間複雜度：O(n)
  • 空間複雜度：O(1)

• 哈希集合法：

  • 時間複雜度：O(n)
  • 空間複雜度：O(n)