Program JavaScript untuk memutar senarai terpaut mengikut arah jam

Struktur asas senarai terpaut dalam JavaScript boleh dibuat menggunakan kelas dalam JavaScript dan kemudian nod boleh dialihkan dari satu kedudukan ke kedudukan lain untuk penggiliran. Dalam artikel ini, kita akan belajar cara memutar senarai terpaut mengikut arah jam dalam bahasa pengaturcaraan JavaScript. Kita akan melihat kod untuk pemahaman yang lebih mendalam tentang konsep ini.

Dalam masalah yang diberikan, kami diberi senarai pautan dan kami perlu memutarkannya mengikut arah jam. Ini bermakna, kita perlu meletakkan elemen terakhir dahulu dalam setiap langkah, jika kita perlu memutar k kali, maka kita perlu meletakkan elemen terakhir sebelum kepala atau nod permulaan senarai pautan. Untuk membuat senarai terpaut yang kita lihat sebelum ini, kita memerlukan kelas untuk mengikat data dan penunjuk ke elemen seterusnya.

Struktur senarai terpaut

Contoh

Pertama, kami akan mencipta nod kelas yang akan menyimpan nilai nod semasa dan penunjuk ke nod seterusnya. Selepas itu, kami akan mencipta fungsi tolak untuk membantu mencipta senarai terpaut, dan akhirnya, kami akan mencipta fungsi paparan untuk membantu mencetak senarai terpaut. Jom tengok kod dulu -

// creating the class for the linked list
class Node{
   // defining the constructor for class
   constructor(){
      this.next = null; // pointer to hold the next value 
      this.value = 0; // curent value in the linked list 
   }
}
// defining push function for linked list 
function push(head,data){
   var new_node = new Node();
   new_node.value = data;
   if(head == null){
      return new_node;
   }
   var temp = head;
   while(temp.next != null){
      temp = temp.next;
   }
   temp.next = new_node;
   return head;
}
function display(head){
   var temp = head;
   var values = 0;
   while(temp){   
      values = values + temp.value + " -> ";
      temp = temp.next;
   }
   console.log(values + "null")
}
var head = null;
for(var i = 1;i<6;i++){
   head = push(head,i);
}
display(head)

Dalam kod di atas, kami telah mencipta kelas menggunakan kata kunci kelas dan mencipta bahagian menggunakan kata kunci "ini" untuk menyimpan data dan penunjuk ke nod seterusnya dalam pembina kelas.

Selepas itu, kami mentakrifkan fungsi tolak yang akan mengambil dua parameter, parameter pertama ialah ketua senarai terpaut, dan parameter kedua ialah data nod baharu yang ingin kami tambahkan pada senarai terpaut. Dalam fungsi, kami mencipta nod baharu dan menyimpan nilai di dalamnya. Kami menyemak sama ada kepala kosong (yang bermaksud kami akan menambah elemen pertama) dan kemudian kami hanya akan mengembalikan nod baharu, jika tidak menggunakan gelung kami akan pergi ke penghujung senarai terpaut dan menambah nod baharu di sana.

Penyelesaian masalah

Selepas mencipta kelas dan mentakrifkan fungsi asas yang diperlukan, kami akan beralih ke fungsi utama di mana kami akan mentakrifkan fungsi yang menggerakkan elemen k terakhir ke hadapan senarai terpaut, yang mewakili putaran senarai terpaut. Terdapat dua cara untuk menambahkan elemen k terakhir pada elemen pertama, yang bersamaan dengan putaran kanan senarai terpaut, cth. -

Kami diberi senarai pautan: 1 -> 2 -> 3 -> 4 -> 5 ->null

Kami mahu memutar pautan yang disenaraikan sekali mengikut arah jam supaya kelihatan seperti ini -

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

Begitu juga, untuk 3 putaran senarai terpaut, senarai terpaut akan kelihatan seperti ini -

Initially Linked list: 1 -> 2 -> 3 -> 4 -> 5 -> null
After the first rotation: 5 -> 1 -> 2 -> 3 -> 4 -> null
After the second rotation: 4 -> 5 -> 1 -> 2 -> 3 -> null
After the third rotation: 3 -> 4 -> 5 -> 1 -> 2 -> null

Kami mempunyai dua cara untuk menambah elemen terakhir di hadapan senarai terpaut, sama ada satu demi satu atau sekaligus.

Putar senarai terpaut satu demi satu

Contoh

Dalam kaedah ini kita akan pergi ke nod terakhir dan kemudian mengalihkannya ke nod kepala sebelumnya dan mengemas kini nod kepala. Mari lihat kod dahulu -

// creating the class for linked list
class Node{
   // defining the constructor for class
   constructor(){
      this.next = null; // pointer to hold the next value 
      this.value = 0; // curent value in the linked list 
   }
}
// defining push function for linked list 
function push(head,data){
   var new_node = new Node();
   new_node.value = data;
   if(head == null){
      return new_node;
   }
   var temp = head;
   while(temp.next != null){
      temp = temp.next;
   }
   temp.next = new_node;
   return head;
}

function display(head){
   var temp = head;
   var values = 0
   while(temp){
      values =  values + temp.value + " -> ";
      temp = temp.next;
   }
   console.log(values + "null")
}
function rotate(head, k){
   while(k--){
      var temp = head;
      while(temp.next.next != null){
         temp = temp.next;
      }
      var new_head = temp.next;
      temp.next = null;
      new_head.next = head;
      head = new_head;
   }
   return head;
}
var head = null;
for(var i = 1;i<6;i++){
   head = push(head,i);
}
head = rotate(head,3);
display(head);

Dalam kod di atas, kami menggunakan kod senarai terpaut fungsi asas yang ditakrifkan di atas dan hanya menambah fungsi baharu untuk memutar senarai terpaut.

Dalam putaran fungsi, kami mula-mula melintasi senarai terpaut k kali menggunakan gelung sementara, dan dalam setiap lelaran, kami mencapai elemen kedua terakhir senarai terpaut. Kemudian kami mengalih keluar elemen terakhir senarai terpaut daripada senarai terpaut dan meletakkannya di hadapan kepala senarai terpaut. Akhir sekali, kami mengembalikan pengepala baharu dan memaparkan senarai terpaut baharu menggunakan fungsi paparan.

Kerumitan masa dan ruang

Kami telah mengalihkan senarai terpaut k kali, dan saiz senarai terpaut ialah N, jadi kerumitan masa keseluruhan program ialah O(N*K). Selain itu, kami tidak menggunakan sebarang ruang tambahan, jadi kerumitan ruang program ialah O(1), iaitu pemalar.

Putar senarai pautan sekali

Dalam kod sebelumnya, kami menambah elemen satu demi satu, yang mengambil masa O(N*N), supaya kami boleh mengalihkan senarai terpaut dengan lebih baik dan mendapatkan saiz senarai terpaut. Selepas itu, kami akan melintasi senarai terpaut sekali lagi dan mendapatkan elemen k terakhir dan menambahkannya ke hadapan senarai terpaut, yang akan menjadikan kerumitan masa program O(1).

Kesimpulan

Dalam tutorial ini, kami mempelajari cara memutar senarai terpaut mengikut arah jam dalam bahasa pengaturcaraan JavaScript. Kami telah melihat kod untuk memahami konsep secara mendalam. Struktur asas senarai terpaut dalam JavaScript boleh dibuat menggunakan kelas dalam JavaScript, dan nod kemudiannya boleh dialihkan dari satu kedudukan ke kedudukan lain untuk penggiliran. Kerumitan masa program ialah O(N*N), yang boleh dipertingkatkan lagi kepada O(N), manakala kerumitan ruang program ialah O(1).

Atas ialah kandungan terperinci Program JavaScript untuk memutar senarai terpaut mengikut arah jam. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!