目錄鏈接：http://www.reibang.com/p/9c0ada9e0ede
環(huán)形鏈表
環(huán)形鏈表(Linked List Cycle)
給定一個(gè)鏈表襟士，判斷鏈表中是否有環(huán)姥宝。
為了表示給定鏈表中的環(huán)却汉，我們使用整數(shù) pos 來(lái)表示鏈表尾連接到鏈表中的位置（索引從 0 開始）哟绊。 如果 pos 是 -1糙箍，則在該鏈表中沒有環(huán)号枕。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個(gè)環(huán)懂更，其尾部連接到第二個(gè)節(jié)點(diǎn)锌订。
</pre>
示例 2：
輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個(gè)環(huán)竹握，其尾部連接到第一個(gè)節(jié)點(diǎn)。
示例 3：
輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環(huán)辆飘。
切題
一啦辐、Clarification
本題沒有什么需要注意的邊界條件谓传，目標(biāo)也很簡(jiǎn)單判斷鏈表是否成環(huán)
二、Possible Solution
1芹关、存儲(chǔ)記錄
這應(yīng)該是比較容易想到的续挟，將我們遍歷的節(jié)點(diǎn)記錄下來(lái)，然后每次新節(jié)點(diǎn)都看它是否已經(jīng)被記錄侥衬，如果沒有就將其記錄下來(lái)诗祸，如果有表示鏈表成環(huán)，如果到了鏈表末尾到?jīng)]有重復(fù)記錄表示鏈表沒有環(huán)
python的話可以用set來(lái)記錄節(jié)點(diǎn)轴总，其時(shí)間復(fù)雜度為 O(n)
2直颅、快慢指針
兩個(gè)指針循環(huán)遍歷鏈表，慢指針每次循環(huán)移一步快指針每次循環(huán)移兩步怀樟，如果鏈表遍歷結(jié)束之前存在快慢指針指向同一節(jié)點(diǎn)則鏈表成環(huán),如果快或慢指針到達(dá)鏈表結(jié)尾且沒相遇表示鏈表無(wú)環(huán)功偿，其時(shí)間復(fù)雜度為 O(n)
Python3 實(shí)現(xiàn)
1、存儲(chǔ)記錄 實(shí)現(xiàn) Py3
環(huán)形鏈表(Linked List Cycle) Py3 存儲(chǔ)記錄 實(shí)現(xiàn)
# @author:leacoder
# @des: 存儲(chǔ)記錄 環(huán)形鏈表
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
save = set() #用于 存儲(chǔ) 鏈表中每個(gè)節(jié)點(diǎn)地址
cur = head
while cur is not None: #循環(huán)迭代鏈表
if cur in save: #是否有記錄
return True #有返回True
else:
save.add(cur) #存儲(chǔ)記錄cur
cur = cur.next #下移
return False
2往堡、快慢指針 實(shí)現(xiàn) Py3
環(huán)形鏈表(Linked List Cycle) Py3 快慢指針 實(shí)現(xiàn)
# @author:leacoder
# @des: 快慢指針 環(huán)形鏈表
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
fast = slow = head
while fast.next:
slow = slow.next #慢指針 每次移一步
fast = fast.next.next #快指針 每次移二步
if slow == fast:
return True
return False
Java實(shí)現(xiàn)
Java實(shí)現(xiàn)邏輯上與Python3無(wú)區(qū)別
1械荷、存儲(chǔ)記錄 實(shí)現(xiàn) Java
環(huán)形鏈表(Linked List Cycle) Java 存儲(chǔ)記錄 實(shí)現(xiàn)
2、快慢指針 實(shí)現(xiàn) Java
環(huán)形鏈表(Linked List Cycle) Java 快慢指針 實(shí)現(xiàn)
C++實(shí)現(xiàn)
環(huán)形鏈表(Linked List Cycle) C++ 快慢指針 實(shí)現(xiàn)
擴(kuò)展閱讀：
Python3 集合
Python Data Structures
Java 集合框架
Java HashSet api doc from oracle
HashSet 的實(shí)現(xiàn)原理
GitHub鏈接：
https://github.com/lichangke/LeetCode
知乎個(gè)人首頁(yè)：
https://www.zhihu.com/people/lichangke/
簡(jiǎn)書個(gè)人首頁(yè)：
http://www.reibang.com/u/3e95c7555dc7
個(gè)人Blog:
https://lichangke.github.io/
歡迎大家來(lái)一起交流學(xué)習(xí)
