給定一個鏈表掸犬，判斷鏈表中是否有環(huán)。
如果鏈表中有某個節(jié)點绰寞，可以通過連續(xù)跟蹤 next 指針再次到達(dá)纤泵，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)笔呀，我們使用整數(shù)pos來表示鏈表尾連接到鏈表中的位置(索引從 0 開始)幢踏。 如果pos是 -1，則在該鏈表中沒有環(huán)许师。
注意：pos不作為參數(shù)進(jìn)行傳遞,僅僅是為了標(biāo)識鏈表的實際情況房蝉。
如果鏈表中存在環(huán)，則返回true微渠。否則搭幻，返回false。
要求:
使用快慢指針的方法判斷給定鏈表是否有環(huán)逞盆，時間復(fù)雜度應(yīng)為 O(N)檀蹋，空間復(fù)雜度應(yīng)為 O(1)。
代碼實現(xiàn)需要定義快慢指針纳击，快指針一次走兩步续扔，慢指針一次走一步,如果快慢指針相遇則說明有環(huán)，實現(xiàn)這一算法焕数。
示例：
輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環(huán)纱昧，其尾部連接到第二個節(jié)點。
答案：
public class ListNode {
public var data: Int
public var next: ListNode?
public init(_ data: Int) {
self.data = data
self.next = nil
}
}
func hasCycle(_ head: ListNode?) -> Bool {
var slow: ListNode? = head
var fast: ListNode? = head
while fast != nil && fast?.next != nil {
slow = slow?.next
fast = fast?.next?.next
if slow === fast {
return true
}
}
return false
}
let node1 = ListNode(1)
let node2 = ListNode(2)
let node3 = ListNode(3)
let node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2 //創(chuàng)建環(huán)堡赔，pos=1
let head = node1
print(hasCycle(head)) //true
知識點詳解：
鏈表：鏈表是一種常見和重要的數(shù)據(jù)結(jié)構(gòu)识脆，主要有一下幾點需要理解：
- 鏈表由一系列節(jié)點(Node)組成，每個節(jié)點包含數(shù)據(jù)域data和指針域next善已。
- 數(shù)據(jù)域用于存儲節(jié)點的數(shù)據(jù)灼捂，指針域用于指向下一個節(jié)點。
- 鏈表中的節(jié)點使用指針連成一串换团，每個節(jié)點指針都指向下一個節(jié)點悉稠，這樣就構(gòu)成了鏈表。
- 鏈表有一個頭節(jié)點
head艘包，作為鏈表的入口的猛，頭節(jié)點不存儲數(shù)據(jù)。(鏈表也可以沒有頭節(jié)點)
(單)鏈表.png
pos：表示鏈表尾部連接到鏈表中的位置(索引從0開始)想虎。也就是說卦尊，如果鏈表中有環(huán)，pos就表示環(huán)的入口節(jié)點的索引舌厨。例如：pos默認(rèn)-1岂却，表示沒有環(huán)，如果再第一個節(jié)點上有環(huán)那么pos就是0裙椭，pos=1那么第二個節(jié)點就是環(huán)的入口躏哩，pos=2環(huán)的入口在第三個節(jié)點上，以此類推...pos不會作為輸入?yún)?shù)傳入函數(shù)揉燃，僅僅表示了鏈表是否有環(huán)以及環(huán)的入口在鏈表中的位置震庭。實際上，我們不需要知道pos的具體值你雌，只需要通過快慢指針判斷鏈表是否存在環(huán)即可器联。
===：三個等號操作符表示指針比較，判斷兩個指針是否指向同一個節(jié)點婿崭。
算法思路
- 定義快慢兩個指針fast和slow拨拓，初始化都指向頭節(jié)點head。
- 每次快指針fast向前移動兩步氓栈，慢指針slow向前移動一步渣磷。
- 檢查快慢指針是否相遇，如果
fast === slow授瘦，則說明鏈表有環(huán)醋界。 - 如果快指針遇到null竟宋，說明鏈表無環(huán)。
時間復(fù)雜度分析：
0.快指針走的速度是慢指針的兩倍
1.在環(huán)外的時候慢指針在后形纺，快指針在前丘侠，不可能重合
2.在環(huán)內(nèi)，快指針走幾步追上了慢指針逐样。
3.快指針到末尾還沒相遇蜗字，說明無環(huán)。
結(jié)論：時間復(fù)雜度O(N)脂新。
空間復(fù)雜度
該算法僅使用了兩個額外的指針：快指針fast和慢指針slow挪捕，空間消耗都是常數(shù)級的，不隨鏈表長度N增加而改變争便〖读悖空間復(fù)雜度是O(1)。
BTW
這道題的題目分析滞乙、要求和示例與題目無關(guān)妄讯，??
感謝各位簡友的寶貴時間與意見！文章難免有疏漏或錯誤酷宵，如有涉及不當(dāng)之處亥贸，還望能夠提出寶貴意見。感激不盡浇垦！
