首页　>　文章列表　>　JavaScript 程序检查单链表是否是回文

JavaScript 程序检查单链表是否是回文

342 2023-09-10

单向链表是一种线性数据结构，它以不连续的方式存储在内存中，每个块通过保存下一个块的地址（也称为节点）来连接。回文可以解释为一组字符、数字等，并且从正面和背面读起来都是一样的。我们将得到一个单链表，并且必须从正面和背面查找节点存储的值是否相等。

输入

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