check_cycle_in_inifinite_single_linked_list.go

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))
	}
}