Program JavaScript untuk menukar nod dalam senarai terpaut tanpa bertukar data

Program JavaScript untuk menukar nod dalam senarai terpaut tanpa bertukar data adalah masalah biasa dalam pembangunan web yang melibatkan penyusunan semula susunan nod dalam senarai terpaut. Senarai terpaut ialah struktur data yang terdiri daripada nod, setiap nod mengandungi sekeping data dan rujukan kepada nod seterusnya dalam senarai.

Dalam artikel ini, kita akan mempelajari tutorial lengkap tentang menukar nod dalam senarai terpaut tanpa menukar data menggunakan JavaScript. Jadi mari kita tentukan nod pertukaran dahulu dan kemudian teruskan dengan tutorial. Jadi, teruskan belajar!

Tukar Nod

Menukar nod dalam senarai terpaut bermakna kita menukar kedudukan dua nod. Terdapat banyak cara untuk menukar nod dalam senarai terpaut. Satu pendekatan ialah menukar data merentas nod, tetapi ini boleh menjadi tidak cekap apabila berurusan dengan jumlah data yang besar. Pendekatan lain ialah menukar penunjuk kepada nod. Ini lebih cekap kerana kami tidak perlu menyalin sebarang data.

Mari kita memahami nod pertukaran melalui contoh

Contoh

Andaikan kami mempunyai senarai pautan seperti di bawah -

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

Kami ingin menukar nod kedua dan keempat untuk mendapatkan:

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

Untuk mencapai ini tanpa menukar data dalam nod, kita perlu mengubah suai pautan antara nod. Senarai terpaut yang terhasil harus mempunyai data yang sama seperti senarai terpaut asal, tetapi dengan susunan nod berubah.

Jadi, kami mula-mula mengenal pasti dua nod untuk ditukar: Nod 2 dan Nod 4. Kita juga perlu menjejaki nod sebelum dan selepas nod ini dalam senarai.

Dalam contoh ini, nod sebelum dan selepas nod 2 masing-masing adalah 1 dan 3. Nod sebelum dan selepas nod 4 masing-masing adalah 3 dan 5.

Seterusnya, kita perlu mengemas kini pautan antara nod. Kami mula-mula menetapkan penunjuk seterusnya nod sebelum nod 2 kepada nod 4. Kami kemudian menetapkan penuding seterusnya nod 2 kepada nod 5 (memandangkan nod 4 kini berada di belakang nod 2). Akhir sekali, kami menetapkan penuding seterusnya nod 4 kepada nod 3 (memandangkan nod 2 kini berada di belakang nod 4).

Senarai pautan yang dijana kelihatan seperti ini -

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

Nota - Data dalam setiap nod tidak berubah, hanya susunan nod.

Sekarang mari kita lihat algoritma yang akan kita gunakan untuk menukar nod dalam senarai terpaut tanpa bertukar data.

Algoritma

LANGKAH1: Kenal pasti dua nod yang perlu ditukar

Langkah pertama ialah mengenal pasti dua nod yang perlu ditukar. Katakan kita ingin menukar nod A dan nod B.

Langkah 2: Cari nod sebelumnya bagi dua nod untuk ditukar

Kita perlu mencari nod sebelum nod A dan B dalam senarai terpaut. Kami memanggil nod ini PrevA dan PrevB masing-masing.

Langkah 3: Kemas kini penuding seterusnya nod sebelumnya untuk menghala ke nod lain

Kini, kita perlu mengemas kini petunjuk seterusnya PrevA dan PrevB untuk menunjuk ke nod yang betul. Ini melibatkan pengemaskinian penuding PrevA seterusnya untuk menghala ke nod B, dan mengemas kini penuding seterusnya PrevB untuk menghala ke nod A.

Langkah 4: Kemas kini penuding seterusnya nod yang akan ditukar supaya ia menghala ke nod yang betul

Seterusnya, kita perlu mengemas kini penunjuk seterusnya nod A dan B untuk menunjuk ke nod yang betul. Ini melibatkan pengemaskinian penunjuk seterusnya nod A untuk menunjuk ke nod bersebelahan nod B, dan mengemas kini penunjuk seterusnya nod B untuk menghala ke nod di sebelah nod A.

Langkah 5: Ulangi langkah di atas untuk mana-mana nod lain yang perlu ditukar

Jika kita perlu menukar lebih daripada dua nod, kita boleh mengulangi langkah di atas untuk setiap pasangan nod yang perlu ditukar.

Selepas melengkapkan langkah ini, nod dalam senarai terpaut akan ditukar, tetapi bukan datanya. Marilah kita memahami algoritma di atas dengan contoh pelaksanaannya menggunakan Javascript.

Contoh

Dalam program ini, kami mula-mula mentakrifkan kelas "Nod" untuk mencipta nod senarai terpaut dan mentakrifkan kelas "LinkedList" untuk mencipta dan mengendalikan senarai terpaut. Fungsi "swapNodes" dalam kelas "LinkedList" melaksanakan algoritma swap yang diterangkan sebelum ini.

// Define a Node class to create nodes of linked list
class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
// Define a LinkedList class to create and manipulate the linked list
class LinkedList {
   constructor() {
      this.head = null;
   }
   // Function to swap two nodes in the linked list
   swapNodes(node1, node2) {
      // If both nodes are the same, no need to swap
      if (node1 === node2) {
         return;
      }
      // Find the previous nodes of both nodes to be swapped
      let prevNode1 = null;
      let currentNode1 = this.head;
      while (currentNode1 && currentNode1 !== node1) {
         prevNode1 = currentNode1;
         currentNode1 = currentNode1.next;
      }
      let prevNode2 = null;
      let currentNode2 = this.head;
      while (currentNode2 && currentNode2 !== node2) {
         prevNode2 = currentNode2;
         currentNode2 = currentNode2.next;
      }
      // If either node1 or node2 is not found, return
      if (!currentNode1 || !currentNode2) {
         return;
      }
      // Update the next pointers of the previous nodes to point to the other node
      if (prevNode1) {
         prevNode1.next = currentNode2;
      } else {
         this.head = currentNode2;
      }
      if (prevNode2) {
         prevNode2.next = currentNode1;
      } else {
         this.head = currentNode1;
      }
      // Swap the next pointers of the nodes to be swapped to point to the correct nodes
      let temp = currentNode1.next;
      currentNode1.next = currentNode2.next;
      currentNode2.next = temp;
      // Print the swapped linked list
      console.log("Swapped linked list:");
      let current = this.head;
      while (current) {
         process.stdout.write(current.data + " -> ");
         current = current.next;
      }
      console.log("null");
   }
   // Function to add a Node at the end of the linked list
   addNode(data) {
      let node = new Node(data);
      if (!this.head) {
         this.head = node;
      } else {
         let current = this.head;
         while (current.next) {
            current = current.next;
         }
         current.next = node;
      }
   }
}
// Create a linked list
let linkedList = new LinkedList();
linkedList.addNode(1);
linkedList.addNode(2);
linkedList.addNode(3);
linkedList.addNode(4);
// Print the original linked list
console.log("Original linked list:");
let current = linkedList.head;
while (current) {
   process.stdout.write(current.data + " -> ");
   current = current.next;
}
console.log("null");
// Swap node 2 and node 4
let node2 = linkedList.head.next;
let node4 = linkedList.head.next.next.next;
linkedList.swapNodes(node2, node4);

Kesimpulan

Dalam tutorial ini, kami menunjukkan program JavaScript yang melaksanakan algoritma ini, yang berjaya menukar nod dalam senarai terpaut tanpa menukar data mereka. Semoga ini membantu pembaca kami. Selamat belajar!

Atas ialah kandungan terperinci Program JavaScript untuk menukar nod dalam senarai terpaut tanpa bertukar data. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!