DEV Community

Sebastian Leukhin
Sebastian Leukhin

Posted on • Updated on

isPalindrome? (LinkedList)

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:

  1. Choose the right names for variables
  2. Choose the right loop statements: for, while, forEach, reduce etc.
  3. Avoid excess conditions and comparisons for edge cases
  4. 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 ( {
    const prevNode = rightSide;

    rightSide =;
    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 =;
    rightSide = rightSide.prevNode;

  // for odd count of nodes check the middle value
  if (leftSide.current === rightSide.current) {
    return true;

  return false;
Enter fullscreen mode Exit fullscreen mode

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;

    // 9 -> 8 -> 7
    const prevLinkedList = currentNode;

    currentNode = {
      current: currentCharacter,
      next: prevLinkedList,

  return currentNode;
Enter fullscreen mode Exit fullscreen mode

Some input data for assertions

Enter fullscreen mode Exit fullscreen mode

Let me know your thoughts in the comment section below! :)

Top comments (0)