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

注意 − 每个节点中的数据没有改变，只是节点的顺序发生了变化。

现在让我们看一下我们将在交换链表中的节点时使用的算法。

步骤

步骤1 ：找到需要交换的两个节点

第一步是找到需要交换的两个节点。假设我们要交换节点A和节点B。

步骤2 ：找到需要交换的两个节点的前面的节点

我们需要找到在链表中节点A和节点B之前的节点。分别称这些节点为PrevA和PrevB。

步骤3 : 更新前面节点的下一个指针，指向另一个节点

现在，我们需要更新PrevA和PrevB的下一个指针，使其指向正确的节点。这涉及将PrevA的下一个指针更新为节点B，并将PrevB的下一个指针更新为节点A。

步骤4 : 更新要交换的节点的下一个指针，使其指向正确的节点

接下来，我们需要更新节点A和B的下一个指针，使其指向正确的节点。这涉及将节点A的下一个指针更新为节点B的下一个节点，将节点B的下一个指针更新为节点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);