用於在不交換資料的情況下交換鍊錶中的節點的 JavaScript 程序

在不交換資料的情況下交換鍊錶中的節點的 JavaScript 程式是 Web 開發中的一個常見問題，涉及重新排列鍊錶中的節點順序。鍊錶是一種由節點組成的資料結構，每個節點包含一條資料和對清單中下一個節點的參考。

在本文中，我們將學習有關在不使用 JavaScript 交換資料的情況下交換鍊錶中的節點的完整教程。因此，讓我們先定義交換節點，然後繼續本教學。所以，繼續學習！

交換節點

交換鍊錶中的節點意味著我們交換兩個節點的位置。有多種方法可以交換鍊錶中的節點。一種方法是交換節點中的數據，但在處理大量數據時，這可能效率低。另一種方法是交換節點的指標。這更有效，因為我們不需要複製任何資料。

讓我們透過一個範例來了解交換節點

範例

假設我們有一個如下所示的連結列表 -

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

我們想要交換第二個和第四個節點以獲得：

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

為了在不交換節點中資料的情況下完成此操作，我們需要修改節點之間的連結。產生的鍊錶應該具有與原始鍊錶相同的數據，但節點的順序發生了變化。

因此，我們首先確定要交換的兩個節點：節點 2 和節點 4。我們還需要追蹤清單中這些節點之前和之後的節點。

本例中，節點2之前和之後的節點分別為1和3。節點4之前和之後的節點分別是3和5。

接下來，我們需要更新節點之間的連結。我們首先將節點 2 之前的節點的下一個指標設定為節點 4。然後，我們將節點 2 的下一個指標設定為節點 5（因為節點 4 現在位於節點 2 之後）。最後，我們將節點 4 的下一個指標設定為節點 3（因為節點 2 現在位於節點 4 之後）。

產生的連結列表如下所示 -

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

注意 - 每個節點中的資料沒有改變，只是節點的順序。

現在讓我們看看我們將用於在不交換資料的情況下交換鍊錶中的節點的演算法。

演算法

STEP1：辨識需要交換的兩個節點

第一步是辨識需要交換的兩個節點。假設我們要交換節點 A 和節點 B。

第2步：找到要交換的兩個節點的前一個節點

我們需要找到鍊錶中節點 A 和 B 之前的節點。我們分別將這些節點稱為 PrevA 和 PrevB。

第3步：更新前一個節點的next指標指向另一個節點

現在，我們需要更新 PrevA 和 PrevB 的 next 指標以指向正確的節點。這涉及更新 PrevA 的 next 指標以指向節點 B，以及更新 PrevB 的 next 指標以指向節點 A。

第4步：更新要交換的節點的next指針，使其指向正確的節點

接下來，我們需要更新節點 A 和 B 的 next 指標以指向正確的節點。這涉及到更新節點 A 的 next 指標以指向節點 B 的下一個節點，以及更新節點 B 的 next 指標以指向節點 A 的下一個節點。

第 5 步：對需要交換的任何其他節點重複上述步驟

如果我們需要交換兩個以上的節點，我們可以對每對需要交換的節點重複上述步驟。

完成這些步驟後，鍊錶中的節點將被交換，但不會交換其資料。現在讓我們透過一個使用 Javascript 實作該演算法的範例來理解上述演算法。

範例

在這個程式中，我們先定義一個「Node」類別來建立鍊錶的節點，並定義一個「LinkedList」類別來建立和操作鍊錶。 “LinkedList”類別中的“swapNodes”函數實作了前面描述的交換演算法。

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

結論

在本教程中，我們展示了一個實作該演算法的 JavaScript 程序，它成功地交換了鍊錶中的節點，而無需交換其資料。希望對我們的讀者有幫助。快樂學習！

以上是用於在不交換資料的情況下交換鍊錶中的節點的 JavaScript 程序的詳細內容。更多資訊請關注PHP中文網其他相關文章！