数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学JavaScript查找两个链表交点程序
在本教程中，我们将讨论两种查找两个链表交点的方法。第一种方法涉及使用循环，第二种方法涉及使用节点差技术，该技术可在线性时间内工作。
我们将得到两个未排序的链表。请注意，此问题的另一个版本是给我们一个已排序的链表对，并必须找到交点。我们必须找到所有元素在两个链表中都相同的节点。我们将提供带有解释的完整代码。
问题介绍
在这个问题中，我们得到了两个链表，两者都以非排序的方式包含一些数字，我们必须找到在该节点之后所有元素（包括当前节点）都相同的节点。
例如：
If the given linked lists are: List1: 1 -> 3 -> 2 -> 9 -> 3 -> 5 -> 8 List2: 8 -> 1 -> 4 -> 3 -> 5 -> 8 From the given linked lists, we have common points: 3, 5, and 8, and it starts from 3, so we will return 3 as the answer.
如果没有这样的节点存在，即在该节点之后所有元素都相等，则我们将返回null作为结果。
嵌套循环方法
在这种方法中，我们可以使用两个嵌套循环，使用这两个循环，我们可以遍历链表并检查它们是否相同。我们将定义两个链表，并为每个链表在末尾添加一个公共链表，以便使用循环获得它。让我们看看代码：
示例
class Node{
constructor(data){
this.value = data
this.next = null
}
}
// printing the linked list
function print(head){
var temp = head
while(temp != null) {
console.log(temp.value)
temp = temp.next
}
}
function intersection(head1, head2){
var temp1 = head1
while(temp1 != null){
var temp2 = head2
while(temp2 != null){
if(temp1 == temp2){
console.log("The intersection point is: " + temp2.value)
return
}
temp2 = temp2.next
}
temp1 = temp1.next
}
console.log("There is no intersection point")
}
// defining common linked list
var common = new Node(3)
common.next = new Node(5)
common.next.next = new Node(8)
// defining the first linked list
var head1 = new Node(1)
head1.next = new Node(3)
head1.next.next = new Node(2)
head1.next.next.next = new Node(9)
head1.next.next.next.next = common
// defining the second linked list
var head2 = new Node(8)
head2.next = new Node(1)
head2.next.next = new Node(4)
head2.next.next.next = common
// finding the intersection point
intersection(head1, head2)
时间和空间复杂度
上述代码的时间复杂度为O(N*M)，其中N是第一个链表的大小，M是第二个链表的大小。上述代码的空间复杂度为O(1)，因为我们在这里没有使用任何额外的空间。
使用节点差
在这种方法中，我们将获得两个链表的大小，然后计算两个链表节点之间的差值。
然后，我们将较长的链表向前移动差值个节点，然后检查每个节点是否相等。
使用这种技术，我们可以将时间复杂度降低到线性。让我们看看它的代码：
示例
class Node{
constructor(data){
this.value = data
this.next = null
}
}
// printing the linked list
function print(head){
var temp = head
while(temp != null){
console.log(temp.value)
temp = temp.next
}
}
// finding length of the Linked lists
function length(head){
var temp = head
var count = 0
while(temp != null){
count++;
temp = temp.next
}
return count
}
function intersection(head1, head2, diffrence){
var temp1 = head1
var temp2 = head2
// moving first linked list
while(diffrence != 0){
diffrence --
temp1 = temp1.next;
}
while(temp1 != null) {
if(temp1 == temp2){
console.log("The intersection point is: " + temp2.value)
return
}
temp1 = temp1.next
temp2 = temp2.next
}
console.log("There is no intersection point")
}
// defining common linked list
var common = new Node(3)
common.next = new Node(5)
common.next.next = new Node(8)
// defining the first linked list
var head1 = new Node(1)
head1.next = new Node(3)
head1.next.next = new Node(2)
head1.next.next.next = new Node(9)
head1.next.next.next.next = common
// defining the second linked list
var head2 = new Node(8)
head2.next = new Node(1)
head2.next.next = new Node(4)
head2.next.next.next = common
// getting differences of the both linked lists
var difference = length(head1) - length(head2)
// finding the intersection point
intersection(head1, head2, difference)
时间和空间复杂度
上述代码的时间复杂度为O(N+M)，其中N是第一个链表中元素的数量，M是第二个链表中元素的数量。上述代码的空间复杂度为O(1)，因为我们没有使用任何额外的空间。
还有一些其他方法，例如使用哈希映射，在第一个链表中创建循环，以及遍历两个链表的最后一个节点。这些方法也可以在线性时间复杂度内工作。
结论
在本教程中，我们实现了一个JavaScript程序来查找两个链表的交点。我们得到了两个未排序的链表，我们必须找到在该节点之后所有元素在两个链表中都相同的节点。我们看到了两种方法，一种是使用循环，另一种是使用节点差技术，该技术可在线性时间内工作。
浏览量：174
