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都不为null时，比较它们的值，并将较大的值添加到mergedList中。
如果其中一个链表变为null，将另一个链表剩余的节点添加到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();

结论

所以在本教程中，我们讨论了如何以相反的顺序合并两个排序的链表。我们提供了一个程序，通过定义两个类，Node和LinkedList，并实现一个merge()方法来演示这个算法。该方法接受两个排序的链表作为输入，并返回一个以相反顺序排序的新链表。通过按照本教程中的算法和程序进行操作，学习者可以轻松地在JavaScript中合并两个排序的链表。