- 直接遍历链表,使用set做标记位(标记是否已经到达过)
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
type void struct{}
func detectCycle(head *ListNode) *ListNode {
if head==nil||head.Next==nil{
return nil
}
var nodes = map[*ListNode]void{}
for head!=nil{
if _, ok := nodes[head];ok{
return head
}
nodes[head] = void{}
head = head.Next
}
return nil
}
- 快慢指针
- 先用快慢指针判断是否存在环,
- 然后将满指针移动到head,
- 然后以相同的速度同时移动快慢指针,相遇点即为环入口
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func detectCycle(head *ListNode) *ListNode {
if head==nil||head.Next==nil{
return nil
}
var flag = false//是否存在环
var slow = head
var quick = head
for quick!=nil && quick.Next!=nil{
slow = slow.Next
quick = quick.Next.Next
if quick==slow{
flag = true
break
}
}
if flag{
slow = head
for slow!=quick{
slow = slow.Next
quick = quick.Next
}
return slow
}
return nil
}