用于在不交换数据的情况下交换链表中的节点的 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 程序，它成功地交换了链表中的节点，而无需交换其数据。希望对我们的读者有所帮助。快乐学习！