给定一个链表,返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。
如果链表无环,则返回 null。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。
如果 pos 是 -1,则在该链表中没有环。注意,pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。
说明:不允许修改给定的链表。
示例 1:输入:head = [3,2,0,-4], pos = 1 输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:输入:head = [1,2], pos = 0 输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:输入:head = [1], pos = -1 输出:返回 null
解释:链表中没有环。
提示:链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
进阶:是否可以使用 O(1) 空间解决此题?
注意:本题与主站 142 题相同
1、哈希辅助;时间复杂度O(n),空间复杂度O(n)
func detectCycle(head *ListNode) *ListNode {
m := make(map[*ListNode]bool)
for head != nil {
if m[head] {
return head
}
m[head] = true
head = head.Next
}
return nil
}
2、快慢指针;时间复杂度O(n),空间复杂度O(1)
func detectCycle(head *ListNode) *ListNode {
if head == nil {
return nil
}
fast, slow := head, head
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
if fast == slow {
break
}
}
if fast == nil || fast.Next == nil {
return nil
}
slow = head
for fast != slow {
fast = fast.Next
slow = slow.Next
}
return slow
}
3、遍历标记;时间复杂度O(n),空间复杂度O(1)
func detectCycle(head *ListNode) *ListNode {
for head != nil {
if head.Val == math.MaxInt32 {
return head
}
head.Val = math.MaxInt32
head = head.Next
}
return head
}
Medium题目,题目同leetcode 142.环形链表II;类似的题目还有
leetcode 141.环形链表、面试题02.08.环路检测
页面更新:2024-04-27
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号