JavaScript program to check if singly linked list is a palindrome

One-way linked list is a linear data structure that is stored in memory in a discontinuous manner. Each block is stored in memory by saving the address of the next block (also called a node). connect. A palindrome can be interpreted as a set of characters, numbers, etc., and reads the same from the front and back. We will get a singly linked list and have to find whether the values ​​stored by the nodes are equal from the front and back.

enter

1 -> 2 -> 3 -> 3 -> 2 -> 1 -> null

Output

Yes, the given linked list is a palindrome. 

illustrate

We can see that the first and last nodes have the same value, the second and penultimate node have the same value, and so on, with each node having the same distance from the front and back having the same value.

enter

1 -> 2 -> 3 -> 4 -> 2 -> 1 -> null

Output

No, the given linked list is not a palindrome. 

illustrate

Here, the first and second nodes are equal to the last and penultimate nodes respectively, but the nodes after that do not have the same value.

Using the stack

In this method, we first create a linked list using this class and then define some basic functions to add data to the linked list and print the data present in the linked list.

Example

// class to create the structure of the nodes 
class Node{
   constructor(data){
      this.value = data;
      this.next = null;
   }
}

// function to print the linked list
function print(head){
   var temp = head;
   var ans = "";    
   while(temp.next != null){
      ans += temp.value;
      ans += " -> "
      temp = temp.next
   }
   ans += temp.value
   ans += " -> null"
   console.log(ans)
}

// function to add data in linked list 
function add(data, head, tail){
   return tail.next = new Node(data);
}

// function to find the string is palindrome or not
function check(head){
   var temp = head;
   var stack = []; // defining the stack    
   while(temp != null){
      stack.push(temp.value);
      temp = temp.next;
   }    
   temp = head;
   while(temp != null){
      if(temp.value != stack.pop()){
         return false;
      }
      temp = temp.next;
   }
   return true;
}

// defining linked list
var head  = new Node(1)
var tail  = head
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(3,head, tail)
tail = add(2,head, tail)
tail = add(1,head, tail)
console.log("The given linked list is: ")
print(head)

// calling function to check if the current linked list is a palindrome or not 
if(check(head)){
   console.log("Yes, the given linked list is a palindrome");
}
else{
   console.log("No, the given linked list is not a palindrome");
}

Time and space complexity

The time complexity of the above code is O(N), where N is the length of the linked list.

The space complexity of the above code is O(N) because we use a stack data structure to store the elements in it.

Use recursion

In this method, we first find the length of the given linked list and then use recursion to traverse to the middle of the linked list. If the length of the given linked list is odd, we will return the next to the middle node, otherwise we will return the middle node, and for each call we will get the corresponding node from behind from the recursive call.

Example

// class to create the structure of the nodes 
class Node{
   constructor(data){
      this.value = data;
      this.next = null;
   }
}

// function to print the linked list
function print(head){
   var temp = head;
   var ans = "";    
   while(temp.next != null){
      ans += temp.value;
      ans += " -> "
      temp = temp.next
   }
   ans += temp.value
   ans += " -> null"
   console.log(ans)
}

// function to add data in linked list 
function add(data, head, tail){
   return tail.next = new Node(data);
}

// recursive function 
function recursion(head, number, odd){
   if(number == 0){
      if(odd){
         return head.next;
      }
      else{
         return head;
      }
   }
   var temp = recursion(head.next, number-1, odd);
   
   // if the current value is not equal then don't move to the next node
   
   // by this we will not reach null in the end 
   
   // indicated the not palindrome 
   
   if(temp.value != head.value){
      return temp;
   }
   else{
      return temp.next;
   }
}

// function to check if the given linked list is palindrome or not 
function check(head){
   var temp = head;
   var len = 0;

   // finding the length of the given linked list 
   while(temp != null){
      len++;
      temp = temp.next;
   }

   // calling the recursion function 
   if(recursion(head, Math.floor(len/2), len & 1) == null){
      return true;
   }
   else{
      return false;
   }
}

// defining linked list
var head  = new Node(1)
var tail  = head
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(4,head, tail)
tail = add(3,head, tail)
tail = add(2,head, tail)
tail = add(1,head, tail)
console.log("The given linked list is: ")
print(head)

// calling function to check if the current linked list is a palindrome or not 
if(check(head)){
   console.log("Yes, the given linked list is a palindrome");
}
else{
   console.log("No, the given linked list is not a palindrome");
}

in conclusion

In this tutorial, we implemented a JavaScript program to check whether a given linked list node contains a value in a palindrome. We implemented two codes using stack and recursion. The time complexity of the stack is O(N) and the space complexity is O(N). The space complexity of the recursive method is O(1) (only when the recursive call data is not consider).

The above is the detailed content of JavaScript program to check if singly linked list is a palindrome. For more information, please follow other related articles on the PHP Chinese website!