單向鍊錶是一種線性資料結構，它以不連續的方式儲存在記憶體中，每個區塊透過保存下一個區塊的位址（也稱為節點）來連接。回文可以解釋為一組字元、數字等，並且從正面和背面讀起來都是一樣的。我們將得到一個單鍊錶，並且必須從正面和背面查找節點儲存的值是否相等。
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)（僅當遞歸呼叫資料為不考慮）。
以上是JavaScript 程式檢查單鍊錶是否為回文的詳細內容。更多資訊請關注PHP中文網其他相關文章！
