今天之題目大意:給你一個單向鏈結串列的頭節點 head,要求判斷這個串列是否存在「環 (cycle)」。所謂環就是某個節點的 next 指標不是指向 null,而是指回前面出現過的節點,導致串列會無限循環走不完。如果存在環就回傳 true,否則回傳 false。
class Solution {
public boolean hasCycle(ListNode head) {
// 使用兩個指標:slow 每次走一步,fast 每次走兩步
ListNode slow = head;
ListNode fast = head;
// 當 fast 或 fast.next 為 null 時,代表已到串列尾部(沒有環)
while (fast != null && fast.next != null) {
slow = slow.next; // slow 向前一步
fast = fast.next.next; // fast 向前兩步
// 如果兩指標相遇,代表存在環
if (slow == fast) {
return true;
}
}
// 跳出迴圈代表 fast 到尾端(沒有環)
return false;
}
}