前言
本题由于没有合适答案为以往遗留问题,最近有时间将以往遗留问题一一完善。
LeetCode - #141 环形链表
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。
难度水平:简单
摘要
在链表问题中,判断链表是否存在环是一个经典问题。本篇文章将介绍如何使用 快慢指针 技巧在 Swift 中实现这一功能,并分析其时间与空间复杂度。我们将从代码、逻辑和测试案例三方面进行讲解,帮助您深入理解这种算法。
描述
给你一个链表的头节点 head
,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos
不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true
。 否则,返回 false
。
示例 1:
输入: head = [3,2,0,-4], pos = 1
输出: true
解释: 链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入: head = [1,2], pos = 0
输出: true
解释: 链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入: head = [1], pos = -1
输出: false
解释: 链表中没有环。
提示:
- 链表中节点的数目范围是
[0, 104]
-105 <= Node.val <= 105
pos
为-1
或者链表中的一个 有效索引 。
进阶: 你能用 O(1)
(即,常量)内存解决此问题吗?
题解答案
我们使用 快慢指针 方法,该方法不仅高效(时间复杂度为 O(n)
),而且空间复杂度为 O(1)
。
核心思路:
- 使用两个指针:快指针 和 慢指针。
- 起始时,两个指针都指向链表的头节点。
- 快指针每次移动两步,慢指针每次移动一步。
- 如果链表中存在环,则快慢指针最终会相遇;如果链表中不存在环,则快指针会先到达链表尾部(
nil
)。
题解代码
以下是 Swift 实现代码:
// 定义链表节点
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) {
self.val = val
self.next = nil
}
}
func hasCycle(_ head: ListNode?) -> Bool {
// 初始化快慢指针
var slow = head
var fast = head
// 快慢指针遍历链表
while let fastNext = fast?.next {
slow = slow?.next // 慢指针走一步
fast = fastNext.next // 快指针走两步
// 如果快慢指针相遇,说明存在环
if slow === fast {
return true
}
}
// 如果遍历到链表末尾,说明不存在环
return false
}
题解代码分析
快慢指针的初始化
- 起始时,快慢指针都指向链表头节点。
- 如果链表为空或只有一个节点,则直接返回
false
。
遍历链表
- 快指针每次移动两步,慢指针每次移动一步。
- 使用
while let
检查快指针的下一个节点是否为nil
,避免越界。
检测环的存在
- 如果快慢指针相遇(
slow === fast
),说明存在环。 - 如果快指针或其下一个节点为
nil
,说明不存在环。
- 如果快慢指针相遇(
时间复杂度
- 每个节点最多被访问两次,时间复杂度为
O(n)
。
- 每个节点最多被访问两次,时间复杂度为
空间复杂度
- 只使用两个指针,额外空间为常量,空间复杂度为
O(1)
。
- 只使用两个指针,额外空间为常量,空间复杂度为
示例测试及结果
以下是测试代码:
// 创建测试用例
func createLinkedListWithCycle(_ values: [Int], _ pos: Int) -> ListNode? {
guard !values.isEmpty else { return nil }
let head = ListNode(values[0])
var current = head
var cycleNode: ListNode? = nil
for i in 1..<values.count {
let node = ListNode(values[i])
current.next = node
current = node
if i == pos {
cycleNode = node
}
}
// 创建环
if let cycleNode = cycleNode {
current.next = cycleNode
}
return head
}
// 示例 1
let head1 = createLinkedListWithCycle([3, 2, 0, -4], 1)
print(hasCycle(head1)) // 输出: true
// 示例 2
let head2 = createLinkedListWithCycle([1, 2], 0)
print(hasCycle(head2)) // 输出: true
// 示例 3
let head3 = createLinkedListWithCycle([1], -1)
print(hasCycle(head3)) // 输出: false
测试结果:
true
true
false
时间复杂度
- 最坏情况:链表中每个节点最多被访问两次,时间复杂度为 O(n),其中
n
是链表节点的数量。
空间复杂度
- 只使用了两个指针(快指针和慢指针),额外空间为 O(1)。
总结
本问题通过 快慢指针 技巧,实现了高效且空间友好的环检测算法。
这种方法不仅适用于链表环检测,还可扩展到许多类似的快慢指针问题,例如寻找环的起始点或判断链表长度是否为偶数。
理解这种算法的核心思想,将为解决链表相关问题奠定坚实基础。
希望这篇文章对您有所帮助!如果您有其他问题,欢迎交流讨论!
关于我们
我们是由 Swift 爱好者共同维护,我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容,也整理收集优秀的学习资料。