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