JavaScript 找到两个排序链表的交集的程序

在这个程序中，我们给定了两个链表，我们需要创建一个新的链表，其中包含两个链表中共有的所有元素。由于这些链表是排序的，所以我们可以使用两个指针的概念来解决这个问题。

问题介绍

在给定的问题中，我们需要找到给定链表的交集。交集意味着获取给定一组值中的共同值，因此我们给定了两个排序链表，我们需要找到两个链表中共有的元素。我们需要返回一个新的链表，并且不改变给定链表的值。

例如：

我们给定了两个排序链表 –

List1: 1 -> 2 -> 4 -> 8 -> 9 -> 11 -> null
List2: 3-> 4 -> 5 -> 7 -> 8 -> 10 -> 11 -> 15 -> 18 -> null

从给定的链接列表中，我们有公共值4、8和11。所以我们需要返回一个排序的链接列表：4 -> 8 -> 11 -> null 如果两个链接列表中没有任何一个值相同，那么我们需要返回一个空的链接列表，即一个空节点或空值。方法我们已经看到了上面的示例，对于当前的问题，我们将使用两个指针的概念。让我们逐步看一下每个步骤，然后再移动到代码的实现- 首先，我们将创建一个类，用于创建链接列表结构，并帮助绑定数据和下一个节点的指针。然后，我们将为给定的链接列表创建三个头节点和一个新的列表来存储答案。同时，我们将创建一个尾节点，用于将值添加到答案链接列表中。我们将创建一个函数来遍历链接列表，一次打印出所有链接列表的值。将有一个push函数，用于将元素添加到链接列表中，该列表将存储答案或额外的链接列表。将使用交集函数来实现主要思想，即两个指针的方法。我们将创建给定的链接列表，然后调用交集函数，然后打印最终的链接列表。两个指针的概念示例在给定的问题中，我们以排序的方式给出了链接列表，所以如果两个链接列表的当前数字相等，我们可以说这是给定链接列表的交集；如果该数字不相等，则具有较小值的链接列表必须向前移动，以便找到匹配的值，并且如果列表到达空值的末尾，则终止搜索。

var heada = null 
var headb = null 
var tail = null 
var extra = null 
// creating a class for developing the linked list nodes  
class Node{
   // constructor to initiate a new node 
   constructor(data){
      this.value = data;
      this.next = null;
   }
}
// Function for printing the complete list
function print(head) {
   var temp = head
   var values = 0
   while (temp != null) {
      values = values + temp.value + " -> ";
      temp = temp.next;
   }
   console.log(values + "null");
}
// Inserting elements into the linked list 
function add(val) {
   var temp_node = new Node(val);
   if (extra == null) {
      extra = temp_node;
      tail = temp_node;
   } 
   else {
      tail.next = temp_node;
      tail = temp_node;
   }
}
// Function for finding the intersection 
// and adding it to the extra list
function intersection() {
   // temporary pointers 
   var tempa = heada 
   var tempb = headb 
   while (tempa != null && tempb != null) {
      if (tempa.value == tempb.value){
         // Add to extra list
         add(tempa.value);
         tempa = tempa.next;
         tempb = tempb.next;
      } 
      else if (tempa.value < tempb.value){
         tempa = tempa.next;
      }else
      tempb = tempb.next;
   }
}
// creating the first linked list 
heada = new Node(1);
heada.next = new Node(2);
heada.next.next = new Node(3);
heada.next.next.next = new Node(4);
heada.next.next.next.next = new Node(6);
// Creating the second linked list
headb = new Node(2);
headb.next = new Node(4);
headb.next.next = new Node(6);
headb.next.next.next = new Node(8);
// Function call for intersection
intersection();
// printing the final answer 
console.log("The linked list containing the common items of the linked list is: ");
print(extra);

时间和空间复杂度

以上代码的时间复杂度是O(N)，其中N是链表的大小，因为我们使用两个指针来遍历链表。

以上代码的空间复杂度是O(1)。我们在这里使用了额外的空间，但这个额外的空间用来存储最终的答案，因此不会额外增加空间复杂度。

结论

在本教程中，我们实现了一个JavaScript程序，用于找到两个已排序链表的交集。我们给定了两个链表，我们需要创建一个新的链表，其中包含这两个链表中都存在的元素。由于链表给定已排序，则我们可以使用两个指针的概念。我们的方法的时间复杂度是O(N)，其中N是链表的大小，而给定方法的空间复杂度是O(1)。