141. Linked List Cycle #
题目 #
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
题目大意 #
判断链表是否有环，不能使用额外的空间。
解题思路 #
给 2 个指针，一个指针是另外一个指针的下一个指针。快指针一次走 2 格，慢指针一次走 1 格。如果存在环，那么前一个指针一定会经过若干圈之后追上慢的指针。
代码 #
package leetcode
import (
"github.com/halfrost/leetcode-go/structures"
)
// ListNode define
type ListNode = structures.ListNode
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func hasCycle(head *ListNode) bool {
fast := head
slow := head
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
if fast == slow {
return true
}
}
return false
}