数据结构
网络
关系数据库管理系统(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
