数据结构与算法 · 单选题 · 第 57 题
计算机基础面试八股 · 第 57 题
用快慢指针判断单链表是否有环,需要的额外空间复杂度是?
- AO(n)
- BO(1)
- CO(log n)
- DO(n²)
答案
B B. O(1)
解析
快指针每次走两步,慢指针每次走一步;有环时两者一定会在环内相遇,无环时快指针会先走到链表末尾。整个过程只用两个指针变量,额外空间是常数。用哈希集合记录访问过的节点也能判环,但需要 O(n) 的额外空间。
在线刷这套题:即时判分、错题本、闪卡复习,不用登录就能练。
数据结构与算法 · 单选题 · 第 57 题
用快慢指针判断单链表是否有环,需要的额外空间复杂度是?
B B. O(1)
快指针每次走两步,慢指针每次走一步;有环时两者一定会在环内相遇,无环时快指针会先走到链表末尾。整个过程只用两个指针变量,额外空间是常数。用哈希集合记录访问过的节点也能判环,但需要 O(n) 的额外空间。
在线刷这套题:即时判分、错题本、闪卡复习,不用登录就能练。