JavaScript 检查单链表是否是回文

单链表是一种线性数据结构，以非连续方式存储在内存中，每个块通过保存下一个块的地址连接，也称为节点。回文可以解释为一组字符、数字等，从前面和后面读取结果相同。我们将获得一个单链表，并需要找出节点上存储的值是否从前面和后面都相等。

输入

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

输出

Yes, the given linked list is a palindrome.

解释

我们可以看到第一个和最后一个节点具有相同的值，第二个和倒数第二个节点以此类推，距离头部和尾部相同距离的每个节点具有相同的值。

输入

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

输出

No, the given linked list is not a palindrome.

解释

这里，第一个和第二个节点分别等于最后一个节点和倒数第二个节点，但是之后的节点没有相同的值。

使用堆栈

在这个方法中，我们首先通过使用类来创建一个链接列表，然后将定义一些基本函数来添加数据到链接列表中并打印链接列表中的数据。

示例

// 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");
}

时间和空间复杂度

以上代码的时间复杂度是O(N)，其中N是链表的长度。

以上代码的空间复杂度是O(N)，因为我们使用栈数据结构来存储其中的元素。

使用递归

在这种方法中，我们首先找到给定链表的长度，然后使用递归来遍历到链表的中间。如果给定链表的长度为奇数，则返回中间节点的下一个节点，否则返回中间节点，并且对于每个调用，我们将从递归调用的后面获取相应的节点。

示例

// 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");
}