Implement Floyd's cycle detection algorithm (Tortoise and Hare) to determine if a linked list contains a cycle.
HardProblem Statement
Implement Floyd's cycle detection algorithm (Tortoise and Hare) to determine if a linked list contains a cycle.
Sample Input
Linked List: [1 -> 2 -> 3 -> 4 -> 2 (cycle)]
Sample Output
true
Limits
Time: 2s · Memory: 256 MB
Code Editor
00:00
package main
import "fmt"
type ListNode struct {
val int
next *ListNode
}
func hasCycle(head *ListNode) bool {
// Your code here
}
func main() {
node1 := &ListNode{val: 1}
node2 := &ListNode{val: 2}
node3 := &ListNode{val: 3}
node4 := &ListNode{val: 4}
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2 // Creates a cycle
fmt.Println(hasCycle(node1)) // Expected Output: true
}
Input
Linked List: [1 -> 2 -> 3 -> 4 -> 2 (cycle)]
Expected Output
true