数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究查找两个已排序链表交集的 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
如果两个链表中没有任何值相同，则我们必须返回一个空链表，即只是一个空节点或 null 值。
方法
我们已经看到了上面关于当前问题的示例，在这个问题中，我们将使用双指针的概念。让我们一步一步地看看，然后我们将进入代码的实现：
首先，我们将创建一个类，它将创建链表结构，并将帮助绑定数据和下一个节点的指针。
然后，我们将为给定的链表和新的存储答案的链表创建三个头节点。此外，我们将创建一个尾节点以将值添加到答案链表中。
我们将创建一个函数来遍历链表，一次打印链表的所有值。
将有一个 push 函数来向存储答案或额外链表的链表添加元素。
intersection 函数将用于实现主要概念，即双指针方法。
我们将创建给定的链表，然后调用 intersection 函数，之后打印最终的链表。
双指针概念
示例
在给定的问题中，我们以排序的方式给出链表，因此，如果两个链表的当前数字相等，那么我们可以说这是给定链表的交集；如果数字不相等，则较小值的链表必须向前移动，以便找到匹配的值；如果任何链表到达 null 值的末尾，则我们将终止搜索。
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)。
浏览量：179
