Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save nikolaydubina/9dff30c265033a66f22e290f4b36e493 to your computer and use it in GitHub Desktop.
Save nikolaydubina/9dff30c265033a66f22e290f4b36e493 to your computer and use it in GitHub Desktop.
check_cycle_in_inifinite_single_linked_list.go
// πŸŽ„πŸŽ„πŸŽ„πŸŽ„πŸŽ„πŸŽ„πŸŽ„πŸ¦ŒπŸ¦ŒπŸ¦ŒπŸ¦ŒπŸ¦ŒπŸ¦ŒπŸ¦ŒπŸ¦ŒπŸ¦ŒπŸŽ…πŸ»πŸŽπŸŽπŸŽπŸŽ„πŸŽ„πŸŽ„πŸŽ„
// time: O(N)
// space: O(1)
// Go Playground: https://go.dev/play/p/1g8m82vmuuu
// why: Merry Christmas!
package main
import "fmt"
type Node struct {
V string
Next *Node
}
func hasCycle(l *Node) bool {
if l == nil {
return false
}
for two, one, i := l, l.Next, 0; one != nil; i++ {
if one == two {
return true
}
one = one.Next
if (i % 2) == 1 {
two = two.Next
}
}
return false
}
func main() {
a := Node{V: "πŸ₯₯"}
b := Node{V: "πŸ…"}
a.Next = &b
b.Next = &a
tests := []struct {
l *Node
hasCycle bool
}{
{
l: nil,
hasCycle: false,
},
{
l: &Node{V: "πŸŽ„", Next: &Node{V: "πŸŽ…πŸ»", Next: &Node{V: "🦌"}}},
hasCycle: false,
},
{
l: &a,
hasCycle: true,
},
{
l: &b,
hasCycle: true,
},
}
for i, tc := range tests {
fmt.Printf("%d: expected(%t) got(%t), is it okay? %t\n", i, tc.hasCycle, hasCycle(tc.l), tc.hasCycle == hasCycle(tc.l))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment