Program JavaScript untuk menyemak sama ada senarai pautan tunggal adalah palindrom-tutorial js-php.cn

Program JavaScript untuk menyemak sama ada senarai pautan tunggal adalah palindrom

WBOY

Lepaskan： 2023-09-22 13:13:08

ke hadapan

1304 orang telah melayarinya

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

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.

Masuk

1 -> 2 -> 3 -> 3 -> 2 -> 1 -> null

Salin selepas log masuk

Output

Yes, the given linked list is a palindrome.

Salin selepas log masuk

Arahan

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.

Masuk

1 -> 2 -> 3 -> 4 -> 2 -> 1 -> null

Salin selepas log masuk

Output

No, the given linked list is not a palindrome.

Salin selepas log masuk

Arahan

Di sini, nod pertama dan kedua adalah sama dengan nod terakhir dan kedua, tetapi nod selepas itu tidak mempunyai nilai yang sama.

Guna tindanan

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.

Contoh

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

Salin selepas log masuk

Kerumitan masa dan ruang

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.

Gunakan rekursi

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.

Contoh

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

Salin selepas log masuk

Kesimpulan

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!