Skip to content

Instantly share code, notes, and snippets.

@myndzi
Last active September 23, 2018 17:48
Show Gist options
  • Save myndzi/0f64ea4e06cc8065e619e7ae1c1ecfe3 to your computer and use it in GitHub Desktop.
Save myndzi/0f64ea4e06cc8065e619e7ae1c1ecfe3 to your computer and use it in GitHub Desktop.
// entities = { next: linkedListItem, size: numberOfItems }
// linkedListItem = { isDeleted: true/false, next: linkedListItem }
var cur = entities;
for (var i = 0; i < entities.size; i++) {
if (cur.next.value < 0) {
cur.next = cur.next.next;
// bug is that we increase i AND decrease entities.size, which
// causes us to approach the end of the loop from both sides
entities.size--;
} else {
cur = cur.next;
}
}
function constructList(arr) {
var entities = { next: null, size: 0 };
var cur = entities;
arr.forEach(v => {
var obj = { value: v, next: null };
cur.next = obj;
cur = cur.next;
entities.size++;
});
return entities;
}
// negative values are considered deleted
function brokenRemoveDeleted(entities) {
var cur = entities;
for (var i = 0; i < entities.size; i++) {
if (cur.next.value < 0) {
cur.next = cur.next.next;
entities.size--;
} else {
cur = cur.next;
}
}
}
function printResults(entities) {
var results = [], item = entities.next;
while (item !== null) {
results.push(item.value);
item = item.next;
}
console.log(results);
}
// test([n, ....])
function test(arr) {
var entities = constructList(arr);
var size, newSize;
do {
size = entities.size;
printResults(entities);
brokenRemoveDeleted(entities);
newSize = entities.size;
} while (size !== newSize);
}
test([-1, -2, -3, -4, -5].reverse());
test([-1, 1, -2, 1, 1, 1, -3, -4, -5, -6, -7, -8].reverse());
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment