資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學將兩個已排序連結串列合併成逆序的JavaScript程式
在本教程中，我們將學習如何編寫一個JavaScript程式，用於合併兩個已排序的連結串列，使得合併後的連結串列以逆序排列。我們將首先透過一些示例來理解問題陳述。然後，我們將逐步講解解決此問題的方法，包括建立一個函式，該函式接收兩個連結串列作為引數並返回以逆序排列的合併連結串列。我們還將討論不同的方法及其時間複雜度，以幫助您選擇最有效的解決方案。因此，讓我們開始學習如何編寫一個JavaScript程式，以逆序合併兩個已排序的連結串列。
問題陳述
我們得到了兩個按升序排序的連結串列，我們的任務是將它們合併，使得結果連結串列按降序（逆序）排列。讓我們透過一些示例來理解這一點。
示例1
輸入
Linked List 1: 1 -> 3 -> 5 -> 7 -> null Linked List 2: 2 -> 4 -> 6 -> null
輸出
Merged List: 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null (The expected output after merging the two lists in reverse order)
注意 − 合併後的結果連結串列也應該按降序排列。
示例2 − 另一個包含重複值的連結串列示例-
輸入
Linked List 1: 1 -> 3 -> 3 -> 5 -> null Linked List 2: 2 -> 4 -> 6 -> null
輸出
合併列表：6 -> 5 -> 4 -> 3 -> 3 -> 2 -> 1 -> null（將兩個列表按逆序合併後的預期輸出）
注意 − 合併後的列表仍然包含按降序排列的重複值。
現在，讓我們嘗試理解上述問題陳述的演算法。
逆序合併兩個已排序連結串列的演算法
建立一個Node類，用於儲存值和下一個指標。
建立一個LinkedList類，用於儲存頭指標和大小變數。
實現一個add()方法，用於將新節點新增到列表的末尾。
實現一個printList()方法，用於列印列表。
實現一個merge()方法，該方法接收兩個已排序的連結串列作為輸入，並返回一個新的按逆序排序的連結串列。
建立一個空的mergedList和兩個指標list1和list2，它們指向輸入列表的頭。
當list1和list2都不為空時，比較它們的值並將較大的值新增到mergedList。
如果其中一個列表為空，則將另一個列表的剩餘節點新增到mergedList。
反轉mergedList中節點的順序並返回它。
建立兩個連結串列，並使用merge()方法合併它們。
列印輸入和輸出列表。
現在我們瞭解了演算法，讓我們藉助一個示例來了解其實現，在這個示例中，我們將使用Javascript實現此演算法。
示例
該程式定義了兩個類Node和LinkedList來表示連結串列。然後，它定義一個merge()函式，該函式接收兩個已排序的連結串列，並將它們合併成一個新的按逆序排序的連結串列。該函式首先比較兩個列表中節點的值，並將較大的值新增到新列表。一旦其中一個輸入列表用盡，該函式就會將另一個列表中的剩餘節點新增到新列表。最後，該函式反轉新列表中節點的順序並返回它。
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
add(value) {
const node = new Node(value);
if (!this.head) {
this.head = node;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.size++;
}
printList() {
let current = this.head;
let result = '';
while (current) {
result += current.value + ' -> ';
current = current.next;
}
result += 'null';
console.log(result);
}
merge(list1, list2) {
let mergedList = new LinkedList();
while (list1 && list2) {
if (list1.value <= list2.value) {
mergedList.add(list1.value);
list1 = list1.next;
} else {
mergedList.add(list2.value);
list2 = list2.next;
}
}
while (list1) {
mergedList.add(list1.value);
list1 = list1.next;
}
while (list2) {
mergedList.add(list2.value);
list2 = list2.next;
}
let current = mergedList.head;
let previous = null;
let next = null;
while (current) {
next = current.next;
current.next = previous;
previous = current;
current = next;
}
mergedList.head = previous;
return mergedList;
}
}
// Example
const list1 = new LinkedList();
list1.add(1);
list1.add(3);
list1.add(5);
list1.add(7);
const list2 = new LinkedList();
list2.add(2);
list2.add(4);
list2.add(6);
console.log('Linked List 1:');
list1.printList();
console.log('Linked List 2:');
list2.printList();
const mergedList = new LinkedList();
mergedList.head = mergedList.merge(list1.head, list2.head).head;
console.log('Merged List:');
mergedList.printList();
結論
在本教程中，我們討論瞭如何在JavaScript中合併兩個已排序的連結串列，使得結果連結串列以逆序排列。我們提供了一個程式來演示此演算法，該程式透過定義兩個類Node和LinkedList以及實現一個merge()方法來實現，該方法接收兩個已排序的連結串列作為輸入，並返回一個新的按逆序排序的連結串列。透過遵循本教程中概述的演算法和程式，學習者可以輕鬆地在JavaScript中合併兩個已排序的連結串列。
瀏覽量：213
