数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学无需交换数据即可交换链表中节点的 JavaScript 程序
无需交换数据即可交换链表中节点的 JavaScript 程序是 Web 开发中一个常见问题，它涉及重新排列链表中节点的顺序。链表是一种数据结构，由节点组成，每个节点包含一个数据片段和对列表中下一个节点的引用。
在本文中，我们将学习一个关于使用 JavaScript 在链表中交换节点而无需交换数据的完整教程。让我们首先定义节点交换，然后继续本教程。继续学习！
交换节点
在链表中交换节点意味着交换两个节点的位置。在链表中交换节点的方法有很多。一种方法是交换节点中的数据，但这在处理大量数据时效率低下。另一种方法是交换节点的指针。这更有效率，因为我们不需要复制任何数据。
让我们用一个例子来理解交换节点
示例
假设我们有一个如下所示的链表：
1 -> 2 -> 3 -> 4 -> 5
我们想要交换第二个和第四个节点以得到：
1 -> 4 -> 3 -> 2 -> 5
要做到这一点而不交换节点中的数据，我们需要修改节点之间的链接。生成的链表应该与原始链表具有相同的数据，但节点的顺序已更改。
因此，我们首先确定我们要交换的两个节点：节点 2 和节点 4。我们还需要跟踪列表中这两个节点之前和之后的节点。
在本例中，节点 2 之前和之后的节点分别是 1 和 3。节点 4 之前和之后的节点分别是 3 和 5。
接下来，我们需要更新节点之间的链接。我们首先将节点 2 之前节点的 next 指针设置为节点 4。然后，我们将节点 2 的 next 指针设置为节点 5（因为节点 4 现在在节点 2 之后）。最后，我们将节点 4 的 next 指针设置为节点 3（因为节点 2 现在在节点 4 之后）。
生成的链表如下所示：
1 -> 4 -> 3 -> 2 -> 5
注意 - 每个节点中的数据没有改变，只有节点的顺序。
现在让我们看看我们将用于在链表中交换节点而无需交换数据的算法。
算法
步骤 1：确定需要交换的两个节点
第一步是确定需要交换的两个节点。假设我们要交换节点 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 程序，它成功地交换了链表中的节点而无需交换它们的数据。希望对我们的读者有所帮助。学习愉快！
258 次浏览
