Hi, I'm excited to start today the series of blog posts about algorithms in wildlife!
The main goal of posts in this series is an adaptation of the algorithms from sites like codewars, leetcode etc. to real projects.
Let's get started with today's topic isPalindrome algorithm. First off I guess you already heard about it, I mean you know how to check whether strings are palindrome or not, and today we will discuss a little bit more complex example with the LinkedList.
I want to set the rules for complexity like: O(n) time, O(1) space.
Rules for the code:
- Choose the right names for variables
- Choose the right loop statements: for, while, forEach, reduce etc.
- Avoid excess conditions and comparisons for edge cases
- Escape the side effects in your algorithms function, because very often you need to do mutations to decrease space or time complexity
Let's try to do this:
const getIsLinkedListPalindrome = (inputLinkedList) => {
let leftSide = inputLinkedList;
let rightSide = inputLinkedList;
while (rightSide.next) {
const prevNode = rightSide;
rightSide = rightSide.next;
rightSide.prevNode = prevNode;
}
/**
* @description
* wo w ow - input
* w === w
* o === o
* while finish
* w === w
* return
* ww - input
* while finish
* w === w
* return
*/
while (
leftSide.current === rightSide.current &&
// a b c - check the "b" node equality in a left and right sides
leftSide !== rightSide &&
// a a - check the "a" node
leftSide !== rightSide.prevNode
) {
if (leftSide.current !== rightSide.current) {
return false;
}
leftSide = leftSide.next;
rightSide = rightSide.prevNode;
}
// for odd count of nodes check the middle value
if (leftSide.current === rightSide.current) {
return true;
}
return false;
};
Some thoughts about the code above:
You may be noticed that we mutated the input data, that outside of a function and i.e. we have a side effect in our function. I think about it as a trade-off for the O(1) space complexity, otherwise, we should have created a new node for each input node, and our space complexity would increase up to O(n). But we avoid the breaking changes to our input data and just extend the initial structure to the doubly linked list.
P.S. Don't use the reverse function to the second part of the list, it breaks the direction of the input linked list.
Extra materials:
To simplify check the result of a function with the string input, use the stringToLinkedList
const stringToLinkedList = (inputStr = '') => {
if (!inputStr) {
return { next: null, current: null };
}
/**
* @type {{
* next: Object | null,
* current: string | null
* }}
*/
let currentNode = { next: null, current: null };
const lastIndex = inputStr.length - 1;
for (let i = lastIndex; i >= 0; i--) {
const currentCharacter = inputStr[i];
if (i === lastIndex) {
currentNode.current = currentCharacter;
continue;
}
// 9 -> 8 -> 7
const prevLinkedList = currentNode;
currentNode = {
current: currentCharacter,
next: prevLinkedList,
};
}
return currentNode;
};
Some input data for assertions
console.assert(getIsLinkedListPalindrome(stringToLinkedList('racecar')));
console.assert(getIsLinkedListPalindrome(stringToLinkedList('abcba')));
console.assert(getIsLinkedListPalindrome(stringToLinkedList('aa')));
console.assert(getIsLinkedListPalindrome(stringToLinkedList('a')));
console.assert(getIsLinkedListPalindrome(stringToLinkedList()));
console.assert(!getIsLinkedListPalindrome(stringToLinkedList('1121')));
console.assert(!getIsLinkedListPalindrome(stringToLinkedList('book')));
console.assert(!getIsLinkedListPalindrome(stringToLinkedList('ab')));
console.assert(!getIsLinkedListPalindrome(stringToLinkedList('abcdba')));
Let me know your thoughts in the comment section below! :)
Top comments (0)