class ListNode<T> {
    public next: ListNode<T> | null = null;
    constructor(public data: T) {}
}

class LinkedList<T> {
    constructor(public head: ListNode<T> | null = null) {}

    public appendToTail(valueToAppend: T) {
        let nodeToAppend = new ListNode(valueToAppend);
        if (this.head === null) {
            this.head = nodeToAppend;
        } else {
            const getLast = (node: ListNode<T>): ListNode<T> => {
                return node.next ? getLast(node.next) : node;
            }
            let lastNode = getLast(this.head);
            lastNode.next = nodeToAppend;
        }
    }

    public removeNode(position: number) {
        try {
            let currentNode = this.head;
            
            if (position == 0) {
                this.head = currentNode!.next;
            }

            for (let i = 1; i < position; i++) {
                currentNode = currentNode!.next;
            }
            currentNode!.next = currentNode!.next!.next;
        }
        catch (error) {
            throw new Error("Unable to remove Node at position " + position);
        }
    }

    public print() {
        let output = "head: "
        let n = this.head;
        while (n != null) {
            output += "[" + n.data + "] -> "
            n = n.next;
        }
        output += "null";
        return output;
    }
}

function removeDuplicates<T>(input: LinkedList<T>) {
    let foundValues: Array<T> = []
    let nodesToRemove: Array<number> = [];

    let workingNode = input.head;
    let index = 0;
    while (workingNode != null) {
        if (foundValues.includes(workingNode.data)) {
            nodesToRemove.push(index);
        } else {
            foundValues.push(workingNode.data);
        }
        index++;
        workingNode = workingNode.next;
    }
    for (let i = 0; i < nodesToRemove.length; i++) {
        input.removeNode(nodesToRemove[i] - i);
    }
}

function removeDuplicatesNoBuffer<T>(input: LinkedList<T>) {
    let currentNode = input.head;
    let workingNode;

    while (currentNode !== null) {
        workingNode = currentNode;
        while (workingNode !== null) {
            if (workingNode.next !== null && workingNode!.next!.data === currentNode.data) {
               workingNode.next = workingNode!.next!.next;
            } else {
                workingNode = workingNode.next;
            }
        }
        currentNode = currentNode.next;
    }
}

let ll = new LinkedList<number>;
let ll2 = new LinkedList<number>;

for (let i = 0; i < 50; i++) {
    ll.appendToTail(Math.floor((Math.PI * Math.pow(10, i))) % 10)
    ll2.appendToTail(Math.floor((Math.PI * Math.pow(10, i))) % 10)
}

console.log(ll.print()); //outputs: "head: [3] -> [1] -> [4] -> [1] -> [5] -> [9] -> [2] -> [6] -> [5] -> [3] -> [5] -> [8] -> [9] -> [7] -> [9] -> [3] -> [2] -> [8] -> [0] -> [6] -> [4] -> [8] -> [8] -> [0] -> [6] -> [4] -> [8] -> [6] -> [2] -> [6] -> [2] -> [8] -> [0] -> [6] -> [6] -> [2] -> [2] -> [6] -> [2] -> [2] -> [8] -> [4] -> [4] -> [8] -> [0] -> [2] -> [8] -> [0] -> [2] -> [4] -> null"

removeDuplicates(ll);
console.log(ll.print()); //outputs: "head: [3] -> [1] -> [4] -> [5] -> [9] -> [2] -> [6] -> [8] -> [7] -> [0] -> null" 

removeDuplicatesNoBuffer(ll2);
console.log(ll2.print()); //outputs: "head: [3] -> [1] -> [4] -> [5] -> [9] -> [2] -> [6] -> [8] -> [7] -> [0] -> null"