给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数pos来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果pos是 -1，则在该链表中没有环。
注意：pos不作为参数进行传递,仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回true。否则，返回false。
要求:
使用快慢指针的方法判断给定链表是否有环，时间复杂度应为 O(N)，空间复杂度应为 O(1)。
代码实现需要定义快慢指针，快指针一次走两步，慢指针一次走一步,如果快慢指针相遇则说明有环，实现这一算法。
示例：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
答案：
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 //创建环，pos=1
let head = node1
print(hasCycle(head)) //true
知识点详解：
链表：链表是一种常见和重要的数据结构，主要有一下几点需要理解：
- 链表由一系列节点(Node)组成，每个节点包含数据域data和指针域next。
- 数据域用于存储节点的数据，指针域用于指向下一个节点。
- 链表中的节点使用指针连成一串，每个节点指针都指向下一个节点，这样就构成了链表。
- 链表有一个头节点
head，作为链表的入口，头节点不存储数据。(链表也可以没有头节点)
(单)链表.png
pos：表示链表尾部连接到链表中的位置(索引从0开始)。也就是说，如果链表中有环，pos就表示环的入口节点的索引。例如：pos默认-1，表示没有环，如果再第一个节点上有环那么pos就是0，pos=1那么第二个节点就是环的入口，pos=2环的入口在第三个节点上，以此类推...pos不会作为输入参数传入函数，仅仅表示了链表是否有环以及环的入口在链表中的位置。实际上，我们不需要知道pos的具体值，只需要通过快慢指针判断链表是否存在环即可。
===：三个等号操作符表示指针比较，判断两个指针是否指向同一个节点。
算法思路
- 定义快慢两个指针fast和slow，初始化都指向头节点head。
- 每次快指针fast向前移动两步，慢指针slow向前移动一步。
- 检查快慢指针是否相遇，如果
fast === slow，则说明链表有环。 - 如果快指针遇到null，说明链表无环。
时间复杂度分析：
转圈分析.png
0.快指针走的速度是慢指针的两倍
1.在环外的时候慢指针在后，快指针在前，不可能重合
2.在环内，快指针走几步追上了慢指针。
3.快指针到末尾还没相遇，说明无环。
结论：时间复杂度O(N)。
空间复杂度
该算法仅使用了两个额外的指针：快指针fast和慢指针slow，空间消耗都是常数级的，不随链表长度N增加而改变。空间复杂度是O(1)。
BTW
这道题的题目分析、要求和示例与题目无关，🤔
感谢各位简友的宝贵时间与意见！文章难免有疏漏或错误，如有涉及不当之处，还望能够提出宝贵意见。感激不尽！
网友评论