單向鏈表是一種線性數(shù)據(jù)結(jié)構(gòu)，它以不連續(xù)的方式存儲在內(nèi)存中，每個塊通過保存下一個塊的地址（也稱為節(jié)點）來連接。回文可以解釋為一組字符、數(shù)字等，并且從正面和背面讀起來都是一樣的。我們將得到一個單鏈表，并且必須從正面和背面查找節(jié)點存儲的值是否相等。
輸入
1 -> 2 -> 3 -> 3 -> 2 -> 1 -> null
登錄后復(fù)制
輸出
Yes, the given linked list is a palindrome.
登錄后復(fù)制
說明
我們可以看到第一個和最后一個節(jié)點具有相同的值，第二個和倒數(shù)第二個節(jié)點具有相同的值，依此類推，與正面和背面距離相同的每個節(jié)點具有相同的值。
輸入
1 -> 2 -> 3 -> 4 -> 2 -> 1 -> null
登錄后復(fù)制
輸出
No, the given linked list is not a palindrome.
登錄后復(fù)制
說明
這里，第一個和第二個節(jié)點分別等于最后一個和倒數(shù)第二個節(jié)點，但之后的節(jié)點不具有相同的值。
使用堆棧
在這種方法中，我們首先使用該類創(chuàng)建一個鏈表，然后定義一些基本函數(shù)以將數(shù)據(jù)添加到鏈表并打印鏈表中存在的數(shù)據(jù)。
示例
// 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");
}
登錄后復(fù)制
時間和空間復(fù)雜度
上述代碼的時間復(fù)雜度為 O(N)，其中 N 是鏈表的長度。
上述代碼的空間復(fù)雜度為 O(N)，因為我們使用堆棧數(shù)據(jù)結(jié)構(gòu)來存儲其中的元素。
使用遞歸
在這個方法中，我們首先找到給定鏈表的長度，然后使用遞歸遍歷到鏈表的中間。如果給定鏈表的長度為奇數(shù)，我們將返回中間節(jié)點的下一個，否則返回中間節(jié)點，并且對于每次調(diào)用，我們將從遞歸調(diào)用中從后面獲取相應(yīng)的節(jié)點。
示例
// 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");
}
登錄后復(fù)制
結(jié)論
在本教程中，我們實現(xiàn)了一個 JavaScript 程序來檢查給定的鏈表節(jié)點是否包含回文中的值。我們使用堆棧和遞歸實現(xiàn)了兩個代碼，堆棧的時間復(fù)雜度為 O(N)，空間復(fù)雜度為 O(N)，遞歸方法的空間復(fù)雜度為 O(1)（僅當遞歸調(diào)用數(shù)據(jù)為不考慮）。
以上就是JavaScript 程序檢查單鏈表是否是回文的詳細內(nèi)容，更多請關(guān)注www.92cms.cn其它相關(guān)文章！
