https://leetcode-cn.com/problems/linked-list-cycle/

給定一個鏈表，判斷鏈表中是否有環。

如果鏈表中有某個節點，可以通過連續跟蹤 next 指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環。注意：pos 不作為參數進行傳遞，僅僅是為了標識鏈表的實際情況。

如果鏈表中存在環，則返回 true 。 否則，返回 false 。

?

進階：

你能用 O(1)（即，常量）內存解決此問題嗎？

?

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環，其尾部連接到第二個節點。
示例?2：

輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環，其尾部連接到第一個節點。
示例 3：

輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環。
?

提示：

鏈表中節點的數目范圍是 [0, 104]
-105 <= Node.val <= 105
pos 為 -1 或者鏈表中的一個 有效索引 。

?

解題報告：

好巧妙啊。尤其是第二題。

AC代碼：

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:bool hasCycle(ListNode *head) {ListNode* p = head;ListNode* q = head;while(q != NULL && q->next != NULL) {p = p->next;q = q->next->next;if(p == q) return true;}return false;} };

?

https://leetcode-cn.com/problems/linked-list-cycle-ii/

給定一個鏈表，返回鏈表開始入環的第一個節點。?如果鏈表無環，則返回?null。

為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環。注意，pos 僅僅是用于標識環的情況，并不會作為參數傳遞到函數中。

說明：不允許修改給定的鏈表。

進階：

你是否可以使用 O(1) 空間解決此題？
?

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第二個節點。
示例?2：

輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第一個節點。
示例 3：

輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環。
?

提示：

鏈表中節點的數目范圍在范圍 [0, 104] 內
-105 <= Node.val <= 105
pos 的值為 -1 或者鏈表中的一個有效索引

AC代碼：（環形鏈表ii）

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode *detectCycle(ListNode *head) {ListNode *p = head, *q = head;bool has = false;while(q != NULL && q->next != NULL) {p = p->next;q = q->next->next;if(p == q) {has = true;break;}}if(has) {q = head;while(p!=q) {p = p->next;q = q->next;}return q;}else return NULL;} };

參考博客：

講述了各種該類問題的變形和證明：https://www.cnblogs.com/yorkyang/p/10876604.html

（不過那個博客里的代碼有點問題，還是以本博客的為準）

?

總結

以上是生活随笔為你收集整理的【LeetCode - 141142】环形链表（i和ii）（快慢指针，链表）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。