Senarai terpaut sehala ialah struktur data linear yang disimpan dalam ingatan secara tidak berterusan, dengan setiap blok disambungkan dengan menahan alamat blok seterusnya (juga dipanggil nod). Palindrom boleh ditafsirkan sebagai satu set aksara, nombor, dsb., dan dibaca sama dari hadapan dan belakang. Kami akan mendapat senarai pautan tunggal dan perlu mencari sama ada nilai yang disimpan oleh nod adalah sama dari hadapan dan belakang.
1 -> 2 -> 3 -> 3 -> 2 -> 1 -> null
Yes, the given linked list is a palindrome.
Kita dapat melihat bahawa nod pertama dan terakhir mempunyai nilai yang sama, nod kedua dan kedua hingga terakhir mempunyai nilai yang sama, dan seterusnya, setiap nod yang jaraknya sama dari hadapan dan belakang mempunyai nilai yang sama.
1 -> 2 -> 3 -> 4 -> 2 -> 1 -> null
No, the given linked list is not a palindrome.
Di sini, nod pertama dan kedua adalah sama dengan nod terakhir dan kedua, tetapi nod selepas itu tidak mempunyai nilai yang sama.
Dalam kaedah ini, kami mula-mula membuat senarai terpaut menggunakan kelas ini dan kemudian menentukan beberapa fungsi asas untuk menambah data pada senarai terpaut dan mencetak data yang ada dalam senarai terpaut.
// 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");
}
Kerumitan masa kod di atas ialah O(N), dengan N ialah panjang senarai terpaut.
Kerumitan ruang kod di atas ialah O(N) kerana kami menggunakan struktur data tindanan untuk menyimpan elemen di dalamnya.
Dalam kaedah ini, mula-mula kita mencari panjang senarai terpaut yang diberikan dan kemudian melintasi bahagian tengah senarai terpaut menggunakan rekursi. Jika panjang senarai pautan yang diberikan adalah ganjil, kami akan mengembalikan nod di sebelah tengah, jika tidak, kami akan mengembalikan nod tengah, dan untuk setiap panggilan kami akan mendapat nod yang sepadan dari belakang daripada panggilan rekursif.
// 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");
}
Dalam tutorial ini, kami melaksanakan program JavaScript untuk menyemak sama ada nod senarai terpaut yang diberikan mengandungi nilai dalam palindrom. Kami melaksanakan dua kod menggunakan tindanan dan rekursi Kerumitan masa tindanan ialah O(N) dan kerumitan ruang ialah O(N) Kerumitan ruang kaedah rekursif ialah O(1) (hanya apabila data panggilan rekursif tidak dipertimbangkan).
Atas ialah kandungan terperinci Program JavaScript untuk menyemak sama ada senarai pautan tunggal adalah palindrom. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
