資料結構
網路
關係型資料庫管理系統 (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
