---
# System prepended metadata

title: 'LeetCode #141 [Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/)'
tags: [LeetCode, Easy, Linked List, Two Pointer]

---

###### tags: `LeetCode` `Linked List` `Easy` `Two Pointer`
# LeetCode #141 [Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/)
### (Easy)

給定一個鏈結串列，判斷鍊表中是否有環。

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

如果鏈結串列中存在環，則返回 true 。否則，返回 false 。

![](https://i.imgur.com/Hqm1qzo.png)


---

鏈結串列只有兩種情況 : 1. 有環 2. 沒有環(持續探索會探索到nullptr)。

使用兩個探索速度不同的指標(每次探索1與2)進行探索, 若探索較快的指標位置與探索較慢的指標位置相同, 則代表反超一圈, 此時存在環, 回傳true; 若不存在環則會探索到nullptr, while迴圈終止, 回傳false。


---
```
/**
 * 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)return false;
        ListNode *f = head, *s = head;
        while(f&&f->next){
            f=f->next->next;
            s=s->next;
            if(f==s)return true;
        }
        return false;
    }
};
```