給定一個連結清單，判斷連結清單中是否有環。
為了表示給定連結清單中的環，我們使用整數
pos
pos
-1
，則在該連結清單中沒有環。
Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer
pos
pos
-1
, then there is no cycle in the linked list.
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：連結清單中有一個環，其尾部連接配接到第二個節點。 
示例 2：
輸入：head = [1,2], pos = 0
輸出：true
解釋：連結清單中有一個環，其尾部連接配接到第一個節點。 
示例 3：
輸入：head = [1], pos = -1
輸出：false
解釋：連結清單中沒有環。 進階：
你能用 O(1)（即，常量）記憶體解決此問題嗎？
Follow up:
Can you solve it using O(1) (i.e. constant) memory?
解題思路：
從頭節點向後周遊整個連結清單隻要周遊到節點為 null ，就證明不是環形，而如果周遊到一個節點的位址之前存在過就證明有環。
1、哈希表：
解決重複問題最容易想到的資料結構就是哈希表，哈希表添加節點時隻要發現節點已經存在了，證明就有環形連結清單。并且哈希表查找和插入複雜度都為O(1)，但是空間複雜度會随着原連結清單長度而增大:O(n)，總的來說：
- 時間複雜度：O(n)，雖然哈希表的查找和添加操作的時間複雜度是 O(1) ，但是先需要周遊連結清單然後插入，周遊的複雜度是O(n)
- 空間複雜度：O(n)，最多需要儲存連結清單的 n個節點
2、雙指針：
這道題就如同國小跑步問題，假設有兩個人（雙指針）一個快一個慢，不停地向前跑，如果跑得快的那個最後到終點了（遇到空節點 null），就證明是直線跑道（沒有環形連結清單）。
如果是存在環形跑道（環形連結清單）：兩個人一起跑步（雙指針）一個快一個慢，那麼這兩個人因為速度不同，在環形跑道裡跑得快的那個人一定會追上慢的。即兩個指針相遇了，證明存在環形連結清單。
空間複雜度為O(1)，即進階要求的常量記憶體。
哈希表解題：
Java：
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) return false;//如果是空連結清單直接傳回
Set<ListNode> nodeSet = new HashSet<>();//構造哈希表
while (head.next != null) {//連結清單下一個不為空
if (nodeSet.contains(head)) return true;//哈希表包含該節點則存在環形連結清單
nodeSet.add(head);//加入節點
head = head.next;//下移一位
}
return false;
}
} Python：
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head is None:
return False
hashSet=set()#構造集合
while(head.next is not None):
if head in hashSet:#是否已存在
return True
hashSet.add(head)
head=head.next
return False 雙指針解題：
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {//快指針及其下一位是否為空
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {//如果相遇，存在環形連結清單
return true;
}
}
return false;
}
} class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head is None or head.next is None:
return False
slow, fast = head, head
while fast is not None and fast.next is not None:
slow, fast = slow.next, fast.next.next
if slow == fast:
return True
return False 擴充：
python 中is 與 == 差別 ：
is 用于判斷兩個變量引用對象（即記憶體位址）是否為同一個， == 用于判斷引用變量的值是否相等。
而Python出于對性能的考慮，不可變對象、同一代碼塊中的對象、值相同的對象，都不會重複建立，而是直接引用已經存在的對象。
歡迎關注公衆号：愛寫bug，一起學習。