資料結構
網路
關係型資料庫管理系統 (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 次瀏覽
