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

结论

在本教程中，我们实现了 JavaScript 程序来检查给定的链表节点是否包含回文中的值。我们使用栈和递归实现了两个代码，它们的时间复杂度为 O(N)，栈的空间复杂度为 O(N)，递归方法的空间复杂度为 O(1)（仅当不考虑递归调用数据时）。