【作者主頁】siy2333
【專欄介紹】?c語言日寄?：這是一個專注于C語言刷題的專欄，精選題目，搭配詳細題解、拓展算法。從基礎語法到復雜算法，題目涉及的知識點全面覆蓋，助力你系統提升。無論你是初學者，還是進階開發者，這里都能滿足你的需求！
【食用方法】1.根據題目自行嘗試 2.查看基礎思路完善題解 3.學習拓展算法
【Gitee鏈接】資源保存在我的Gitee倉庫：https://gitee.com/siy2333/study

---

---

前言

在數據結構的學習中，鏈表是一種非常常見的線性結構，而環形鏈表問題則是鏈表問題中的經典之一。環形鏈表是指鏈表的尾節點指向鏈表中的某個節點，從而形成一個環。判斷鏈表中是否存在環是許多算法問題的基礎，也是面試中常見的考點。今天，我們就通過一個具體的題目來深入探討如何檢測環形鏈表。

---

題目引入

判斷鏈表中是否有環
給定一個鏈表的頭節點 head，判斷鏈表中是否存在環。如果鏈表中存在環，則返回 true；否則返回 false。

例如：

• 輸入：head = [3,2,0,-4]，pos = 1（pos 表示尾節點連接到鏈表中的位置，從 0 開始）
• 輸出：true
• 解釋：鏈表中存在環，尾節點連接到第二個節點。

這個問題看似簡單，但背后涉及到了鏈表的遍歷、指針操作以及算法的設計。接下來，我們將逐步分析如何解決這個問題。

知識點分析

1. 鏈表的基本概念

鏈表是一種線性數據結構，由一系列節點組成，每個節點包含兩部分：

• 數據域：存儲數據。
• 指針域：存儲指向下一個節點的指針。

對于環形鏈表問題，我們需要特別關注指針域，因為它決定了鏈表的結構。

2. 快慢指針法

解決環形鏈表問題的核心思想是使用快慢指針法。快慢指針法是一種常見的鏈表操作技巧，通過設置兩個指針（一個快指針和一個慢指針）來遍歷鏈表。具體步驟如下：

• 慢指針：每次移動一步。
• 快指針：每次移動兩步。

如果鏈表中存在環，快指針和慢指針最終會在環內相遇；如果鏈表中沒有環，快指針會先到達鏈表的末尾。

3. 指針操作

在鏈表操作中，指針的使用至關重要。我們需要熟練掌握如何通過指針訪問和修改鏈表節點。例如：

• 使用 node->next 訪問下一個節點。
• 使用 node = node->next 移動指針。

在環形鏈表問題中，指針的正確操作是實現快慢指針法的基礎。

注意事項

1. 空鏈表和單節點鏈表

在實現算法時，需要特別注意鏈表為空或只有一個節點的情況。對于這兩種情況，鏈表中顯然不存在環，因此可以直接返回 false。

if (head == NULL || head->next == NULL) {return false;
}

2. 指針越界問題

在鏈表操作中，需要確保指針不會越界。特別是在快指針每次移動兩步時，必須先檢查 fast 和 fast->next 是否為 NULL。

while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;if (slow == fast) {return true;}
}

3. 時間復雜度和空間復雜度

快慢指針法的時間復雜度為 O(n)，其中 n 是鏈表的長度。這是因為快指針最多遍歷鏈表兩次。空間復雜度為 O(1)，因為我們只使用了兩個指針，不需要額外的存儲空間。

拓展應用

1. 找到環的入口

除了判斷鏈表中是否存在環，我們還可以進一步找到環的入口。這是快慢指針法的一個重要拓展應用。

當快指針和慢指針相遇后，我們可以通過以下步驟找到環的入口：

1. 將慢指針重置為鏈表的頭節點。
2. 快指針保持在相遇點。
3. 快指針和慢指針都每次移動一步，直到它們再次相遇。相遇點即為環的入口。

代碼實現如下：

struct ListNode *detectCycle(struct ListNode *head) {if (head == NULL || head->next == NULL) {return NULL;}struct ListNode *slow = head;struct ListNode *fast = head;while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;if (slow == fast) {break;}}if (fast == NULL || fast->next == NULL) {return NULL;}slow = head;while (slow != fast) {slow = slow->next;fast = fast->next;}return slow;
}

2. 判斷環的長度

在找到環的入口后，我們還可以進一步計算環的長度。方法是從環的入口開始，使用一個指針遍歷環，直到再次回到入口。

代碼實現如下：

int cycleLength(struct ListNode *head) {struct ListNode *entry = detectCycle(head);if (entry == NULL) {return 0;}struct ListNode *temp = entry;int length = 0;do {temp = temp->next;length++;} while (temp != entry);return length;
}

總結

通過上述分析和代碼實現，我們詳細探討了如何檢測環形鏈表，并進一步找到了環的入口和環的長度。快慢指針法是一種非常高效且優雅的算法，它不僅能夠解決環形鏈表問題，還可以應用于其他鏈表相關問題。

希望這篇文章能幫助你更好地理解和掌握鏈表操作和快慢指針法。如果你對鏈表或其他數據結構感興趣，可以繼續關注我的博客，我會定期分享更多優質內容。

[專欄鏈接QwQ] :?c語言日寄?CSDN
[關注博主ava]：siy2333
感謝觀看~ 我們下次再見!!