reverse_infinite_single_linked_list.go

reverse_infinite_single_linked_list.go

// Go Playground: https://go.dev/play/p/DMiZPwRUGWD
// time: O(N)
// space: O(1)
// why: Just For Fun! 🤪
package main

import "fmt"

type Node struct {
	V    string
	Next *Node
}

func reverse(l *Node) *Node {
	var rroot *Node
	var next *Node
	for q := l; q != nil; q = next {
		next = q.Next
		q.Next = rroot
		rroot = q
	}
	return rroot
}

func toSlice(l *Node) []Node {
	var ls []Node
	for q := l; q != nil; q = q.Next {
		ls = append(ls, *q)
	}
	return ls
}

func fromSlice(l []Node) *Node {
	if len(l) == 0 {
		return nil
	}

	for i := len(l) - 1; i > 0; i-- {
		l[i-1].Next = &l[i]
	}

	return &l[0]
}

// ignore pointer, care about value only
func eq(a, b []Node) bool {
	if len(a) != len(b) {
		return false
	}
	for i := 0; i < len(a); i++ {
		if a[i].V != b[i].V {
			return false
		}
	}
	return true
}

func main() {
	// lets check pointers!
	ls := []Node{{V: "a"}, {V: "b"}, {V: "c"}}
	l := fromSlice(ls)
	fmt.Printf("debug pointers: before: %#v\n", ls)
	r := reverse(l)
	lr := toSlice(r)
	fmt.Printf("debug pointers: after: %#v\n", lr)

	// lets run tests!
	tests := []struct {
		in  []Node
		out []Node
	}{
		{
			in:  []Node{{V: "a"}, {V: "b"}, {V: "c"}},
			out: []Node{{V: "c"}, {V: "b"}, {V: "a"}},
		},
		{
			in:  []Node{},
			out: []Node{},
		},
	}
	for i, tc := range tests {
		reversed := reverse(fromSlice(tc.in))
		fmt.Printf("%d: passed? %t: before(%#v) after(%#v) expected(%#v)\n", i, eq(toSlice(reversed), tc.out), tc.in, toSlice(reversed), tc.out)
	}
}