fun.go

package main

import (
	"bytes"
	"fmt"
	"strconv"
)

type Node struct {
	next *Node
	val  int
}

type LinkedList struct {
	head *Node
}

func NewLL() *LinkedList {
	return &LinkedList{
		head: nil,
	}
}

func (l *LinkedList) Add(val int) {
	if l.head == nil {
		l.head = &Node{nil, val}
		return
	}

	cur := l.head
	for {
		if cur.next == nil {
			cur.next = &Node{nil, val}
			break
		}
		cur = cur.next
	}
}

func (l *LinkedList) String() string {
	cur := l.head
	buf := bytes.NewBuffer(nil)
	for {
		if cur != nil {
			buf.WriteString(strconv.Itoa(cur.val))
			if cur.next != nil {
				buf.WriteString(", ")
			}
			cur = cur.next
		} else {
			break
		}
	}
	return fmt.Sprintf("[%s]", buf.String())
}

func RemoveMiddleNodeMemoryWise(head *Node) {
	// uses a single node reference and an integer only

	// Traverse the LL to count the number of nodes
	size := countNodes(head, 0)
	// if even, do nothing
	if size%2 == 0 {
		return
	}

	// else remove the middle node
	nodeBeforeRemoval := (size / 2) - 1
	applyAtDepth(head, nodeBeforeRemoval, func(removeNext *Node) {
		toRemove := removeNext.next
		if toRemove == nil {
			return
		}
		removeNext.next = toRemove.next
	})
}

func applyAtDepth(node *Node, depth int, apply func(*Node)) {
	if node == nil {
		panic("traversing depth passed last node")
	}
	if depth <= 0 {
		apply(node)
		return
	}
	applyAtDepth(node.next, depth-1, apply)
}

func countNodes(cur *Node, curCount int) int {
	if cur == nil {
		return curCount
	}
	return countNodes(cur.next, curCount+1)
}

func main() {
	ll := NewLL()

	ll.Add(1)
	ll.Add(2)
	ll.Add(5)
	fmt.Printf("got %s, removing middle ->\n", ll)
	RemoveMiddleNodeMemoryWise(ll.head)
	fmt.Printf("got %s, removing middle again -> \n", ll)

	RemoveMiddleNodeMemoryWise(ll.head)

	fmt.Printf("got %s, adding new value ->\n", ll)

	ll.Add(10)
	fmt.Printf("got %s, removing middle ->\n", ll)
	RemoveMiddleNodeMemoryWise(ll.head)
	fmt.Printf("got %s\n", ll)
}

func RemoveMiddleNodeSpeedWise(head *Node) {
	// Two nodes running, slow and fast.
	// `fast` jumps by steps of two nodes.
	// `slow` jumps by steps of one node.
	// when `fast.next` is `nil`,
	//      deleted nothing : the LL has even number
	// when `fast.next.next` is `nil`,
	//     `slow` is at the node before the one to delete

}