Skip to content

Instantly share code, notes, and snippets.

@stephencweiss
Created December 29, 2018 16:53
Show Gist options
  • Save stephencweiss/1d59d2a75e53f52ec34948e7c7479309 to your computer and use it in GitHub Desktop.
Save stephencweiss/1d59d2a75e53f52ec34948e7c7479309 to your computer and use it in GitHub Desktop.
A method to remove duplicates from a linked list
/**
* removeLinkedListDuplicates: Removes duplicates from an unsorted linked list.
* Return value is a linked list with duplicates removed.
* @param {Object} linkedList - The linkedList to remove duplicates from.
* @param {Object} [currentNode] - The currently evaluated node
* @param {Object} [previouslySeen] - An object storing the values of all previously seen nodes
*/
function removeLinkedListDuplicates(linkedList, currentNode, previouslySeen ) {
currentNode = currentNode || linkedList.head;
previouslySeen = previouslySeen || {};
if (Object.keys(previouslySeen).length === 0) {
previouslySeen[currentNode.value] = 1;
}
if (!currentNode.next) { return linkedList; }
if (previouslySeen[currentNode.next.value]) {
currentNode.next = currentNode.next.next;
if (linkedList.size) { linkedList.size -= 1; }
if (currentNode.next.previous) { currentNode.next.next.previous = currentNode; }
if (!currentNode.next) { return linkedList; }
} else { previouslySeen[currentNode.next.value] = 1; }
return removeDuplicates(linkedList, currentNode.next, previouslySeen)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment