-
-
Save myndzi/0f64ea4e06cc8065e619e7ae1c1ecfe3 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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; | |
} | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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