dedup-recursion.go

package main

import "fmt"

type Node struct {
	Data int
	Next *Node
}

func removeDups(n *Node, seenValues map[int]bool) *Node {
	if n == nil {
		return nil
	} else {
		// if we have seen this value already
		if seenValues[n.Data] {
			return removeDups(n.Next, seenValues)
		} else {
			seenValues[n.Data] = true
			return &Node{n.Data, removeDups(n.Next, seenValues)}
		}
	}
}

func removeDupsWithStore(node *Node) *Node {
	seenValues := map[int]bool{}
	return removeDups(node, seenValues)
}

func main() {

	n1 := Node{Data: 5}
	n2 := Node{Data: 3, Next: &n1}
	n3 := Node{Data: 5, Next: &n2}
	n4 := Node{Data: 3, Next: &n3}
	n5 := Node{Data: 2, Next: &n4}

	resultNode := removeDupsWithStore(&n5)

	for i := resultNode; i != nil; i = i.Next {
		fmt.Printf("result: %d\n", i.Data)
	}

}