CTCI_2.8..go

package main

type node struct {
	value        interface{}
	before, next *node
}

func newNode(val interface{}) *node {
	return &node{
		value: val,
	}
}

func (n *node) appendToTail(v interface{}) {
	end := newNode(v)
	currentNode := n
	for {
		if currentNode.next == nil {
			break
		}
		currentNode = currentNode.next
	}
	currentNode.next = end
	end.before = currentNode
}

func (n *node) makeLoopFrom(targetVal interface{}) {
	currentNode := n
	var firstLoopedNode *node
	for {
		if currentNode.value.(int) == targetVal.(int) {
			firstLoopedNode = currentNode
			break
		}

		if currentNode.next == nil {
			break
		}
		currentNode = currentNode.next
	}

	if firstLoopedNode == nil {
		return
	}

	currentNode = n
	var endNode *node
	for {
		if currentNode.next == nil {
			endNode = currentNode
			break
		}
		currentNode = currentNode.next
	}
	endNode.next = firstLoopedNode
	firstLoopedNode.before = currentNode
}

func returnFirstLoopedNode(targetList *node) *node {
	numOfAppearance := make(map[int][]*node)
	currentNode := targetList

	for {
		if _, found := numOfAppearance[currentNode.value.(int)]; found {
			addresses := numOfAppearance[currentNode.value.(int)]
			for _, addr := range addresses {
				if addr == currentNode {
					return currentNode
				}
			}
		}

		numOfAppearance[currentNode.value.(int)] = append(numOfAppearance[currentNode.value.(int)], currentNode)

		if currentNode.next != nil {
			currentNode = currentNode.next
		} else {
			return nil
		}
	}
}

func main() {
	// 1->2->3->5->2->...
	// 1->2->3->2->5->3->2->5...
	n := newNode(1)
	n.appendToTail(2)
	n.appendToTail(3)
	n.appendToTail(2)
	n.appendToTail(5)
	n.makeLoopFrom(3)

	println(returnFirstLoopedNode(n).value.(int))
}