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)