LeetCode
題目： 環(huán)形鏈表
給定一個(gè)鏈表，判斷鏈表中是否有環(huán)哲银。
進(jìn)階
你能否不使用額外空間解決此題竞端？
方案：
可以轉(zhuǎn)化為一個(gè)追擊問題
前后雙指針，slow走一步饥脑，fast走兩步纠俭，如果有環(huán)存在惊暴，一定會相遇的。
代碼：
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init(_ val: Int) {
* self.val = val
* self.next = nil
* }
* }
*/
extension ListNode: Equatable {
public static func == (lhs: ListNode, rhs: ListNode) -> Bool {
return Unmanaged.passUnretained(lhs).toOpaque() == Unmanaged.passUnretained(rhs).toOpaque()
}
}
class Solution {
func hasCycle(_ head: ListNode?) -> Bool {
if (head == nil || head?.next == nil) {
return false
}
var slow = head
var fast = head?.next
while(slow != fast) {
if (fast == nil || fast?.next == nil) {
return false
}
slow = slow?.next
fast = fast?.next?.next
}
return true
}
}
