Cracking the coding interview 2.1 remove duplicate values from singly linked list javascript

Question

class LinkedListNode {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

let head = new LinkedListNode("head");

let x = [1, 1, 1, 1, 4, 10, 10, 3, 10, 9, 5, 5, 5, 8];

for (let ele of x) {
    let y = new LinkedListNode(ele);
    let pointer = head;
    while (pointer.next != null) {
        pointer = pointer.next;
    }
    pointer.next = y;
}

Can someone explain why the following 'solution' leads to an infinite loop?

let removeDup = function(sll) {
    let array = []
    let pointer = sll;
    while (pointer) {
        if (array.includes(pointer.value)){
        } else {
            array.push(pointer.value);
            sll.next = pointer;
            sll = sll.next;
        }
        pointer = pointer.next;
    }
}

It appears that if I

let pointer = sll.next;

or

let array = [sll.value]

then it works fine but if I run it as is then it leads to an infinite loop. I can see why it may make a linked list with 2 duplicates of the first value but I can't understand why it makes an infinite loop. Alternatively, if anyone can point me in the right direction for debugging this then that would be appreciated also!

Answer 1

Looks like you end up defining a node that references itself within your else condition.

You may be looking for something like this:

class LinkedListNode {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

let head = new LinkedListNode("head");

let x = [1, 1, 1, 1, 4, 10, 10, 3, 10, 9, 5, 5, 5, 8];

for (let ele of x) {
    let y = new LinkedListNode(ele);
    let pointer = head;
    while (pointer.next != null) {
        pointer = pointer.next;
    }
    pointer.next = y;
}

function removeDup(currentNode = sll) {
	const seen = {};
	let lastUnique;
	while (currentNode) {
		if (seen[currentNode.value]) {
			lastUnique.next = currentNode.next;
		} else {
			seen[currentNode.value] = true;
			lastUnique = currentNode;
		}
		currentNode = currentNode.next;
	}
}

removeDup(head);

let outputNode = head;
while (outputNode) {
	outputNode = outputNode.next;
	if (outputNode) {
		console.log(outputNode.value);
	}
}