題目

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

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

為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環。

示例 1：

輸入：head = [3,2,0,-4], pos = 1

輸出：true

解釋：鏈表中有一個環，其尾部連接到第二個節點。

示例 2：

輸入：head = [1,2], pos = 0

輸出：true

解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例 3：

輸入：head = [1], pos = -1

輸出：false

解釋：鏈表中沒有環。

進階：

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

C++代碼

思路：使用快慢指針

慢指針一次移動一個節點

快指針一次移動兩個節點

一旦快指針為NULL，則沒有環，因為能夠找到盡頭

如果有環，那么整個循環過程是無窮盡的，快指針一定會追上慢指針，且不會錯過。

/*** 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) {if(head == NULL || head->next == NULL)return false;ListNode* slow = head;ListNode* fast = head->next;while(slow != fast){if(fast->next == NULL || fast->next->next == NULL)return false;fast = fast->next->next;slow = slow->next;}return true;} };

執行用時: 16ms, 在所有 C++ 提交中擊敗了 54.04% 的用戶

內存消耗: 9.8MB, 在所有 C++ 提交中擊敗了 33.30% 的用戶

總結

以上是生活随笔為你收集整理的leetcode No.141 环形链表的全部內容，希望文章能夠幫你解決所遇到的問題。

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