hce_kmu
112年
計算機概論與程式設計
第 19 題
Given the head of a linked list, determine whether the linked list has a cycle. If it does have a cycle, return true; otherwise, return false. The example and algorithm are shown below.
```c
bool hasCycle(ListNode *head){
if(head==NULL||head->next==NULL)
return false;
ListNode *a=head;
ListNode *b=head->next;
while(a!=b){
if(b==NULL||b->next==NULL)
return false;
// Q1 //
// Q2 //
}
return true;
}
```
Which of the followings should be "Q1" and "Q2" in the algorithm?
```c
bool hasCycle(ListNode *head){
if(head==NULL||head->next==NULL)
return false;
ListNode *a=head;
ListNode *b=head->next;
while(a!=b){
if(b==NULL||b->next==NULL)
return false;
// Q1 //
// Q2 //
}
return true;
}
```
Which of the followings should be "Q1" and "Q2" in the algorithm?
- A Q1: a = a -> next; Q2: b = b -> next;
- B Q1: a = b; Q2: b = b -> next;
- C Q1: a = a -> next; Q2: b = b -> next;
- D Q1: a = a -> next -> next; Q2: b = b -> next;
- E Q1: a = a -> next; Q2: b = b -> next -> next;
思路引導 VIP
想像一下，在操場的環形跑道上有兩個正在賽跑的人：如果兩個人跑的速度完全一樣，且起跑點不同，他們有可能會相撞（相遇）嗎？若要確保在有環的情況下兩人一定能碰面，他們在移動速度的設計上應該具備什麼樣的關係？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精確辨識出這個經典的演算法，展現了你對指標（Pointer）操作與鏈結串列結構的深刻理解。這題考查的是資訊領域非常著名的龜兔賽跑演算法（Floyd's Tortoise and Hare Algorithm）。
快慢指標的追擊原理
在處理鏈結串列（Linked List）是否包含環狀結構時，最有效率的方法就是讓兩個指標以不同的速度移動。選項 (E) 正確地設定了 a 每次向後移動一步，而 b 每次移動兩步。在一個封閉的環中，移動較快的指標 b 最終一定會從後方「追上」移動較慢的指標 a，使得 a == b 的條件成立。反之，若串列中沒有環，快指標 b 就會先遇到 NULL 並跳出迴圈，這正是程式碼中判斷 false 的邏輯。
▼ 還有更多解析內容