題目要求 (高頻題)
給一個連結清單,判斷是否有環存在。為了表示連結清單中的環,我們用一個整數pos來表示環的位置,如果pos等于-1,則表示沒有環。
示例
**Example 1**
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.
**Example 2**
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
解題思路
快慢指針
判斷連結清單中是否存在環是一類非常易考的題目,它通過“快慢”指針的技巧能夠在短時間内找到連結清單中是否存在環。既簡單又高效,隻要判斷快指針是否和慢指針相遇即可。
主要代碼 c++
/**
* 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 *slow = head;
ListNode *fast = head;
while(fast && fast->next) // 判斷為空的情況
{
slow = slow->next;
fast = fast->next->next; //快指針每次走兩步
if(slow==fast) return true; // 若快慢指針相遇 則有環
}
return false; //說明沒環直接到末尾null,有環進while裡
}
};
相似題目
解答:leetcode876. Middle of the Linked List(尋找連結清單的中間元素)