從三個連結串列中查詢和等於給定數字的三元組的 JavaScript 程式

---

在本文中，我們將實現一個 JavaScript 程式，用於從三個連結串列中找到一個三元組，其和等於給定的數字。這個問題是標準且著名的三數之和問題的變體，但它以連結串列的方式呈現。讓我們看看這個問題，並實現其程式碼以及問題的關鍵點。

問題介紹

這個問題是標準的三數之和問題的變體，其中給定三個陣列，我們必須找到陣列中是否存在任何三元組，其和正好等於給定的數字。

在這個問題中，我們得到三個連結串列和一個數字，我們必須從所有連結串列中精確選擇一個元素，並且所選數字的和必須等於給定的數字。

如果所選數字的和等於給定的數字，那麼我們必須返回 true，否則返回 false。

例如 −

如果給定的數字是 10，並且連結串列如下所示 −

List 1: 1 -> 2 -> 3 -> 4 -> 5
List 2: 3 -> 7 -> 8 -> 13
List 3: 9 -> 7 -> 2 -> 8

從上面給定的連結串列中，我們可以選擇以下和為 10 的集合。

如果我們從第一個列表中選擇 1，從第二個列表中選擇 7，從最後一個列表中選擇 2。

或者，我們可以從最後一個列表中選擇 2，從第二個列表中選擇 3，從第一個列表中選擇 5。

因此，在這種情況下，我們將返回 true。

現在想象一下，如果給定的數字很大，例如 25，那麼就沒有三個數字的集合可以滿足條件。

注意 − 我們必須從所有三個給定的列表中精確選擇一個數字。

方法

我們已經看到了這個問題的例子，現在讓我們來看一下程式碼實現的步驟 −

在進入主要方法之前，這裡有一些我們將要做的假設 −

第二個連結串列將按升序排序，而第三個連結串列將按降序排序，因為我們將使用雙指標技術，只有在上述假設為真的情況下才能使用。

如果上述假設不成立，那麼我們還有另一種方法，那就是使用歸併排序技術對第二個連結串列進行排序，這將需要 O(N*log(N)) 的時間複雜度，其中 N 是連結串列的大小。

類似地，對於第三個連結串列，我們可以對其進行排序並反轉，使其成為嚴格遞減的連結串列，這對於大小為 N 的連結串列也需要 O(N*log(N)) 的時間複雜度。

主要方法 −

示例

首先，我們將使用 while 迴圈遍歷第一個連結串列，在每一步中，我們將使用雙指標方法來使所有當前元素的和等於給定數字。

// class for linked list node
class Node{
   constructor(data){
      this.value = data;
      this.next = null;
   }
}
 // function to find the triple or return false if the required number is not found 
function fun(lista,listb,listc,k){
   // creating temporary value of 
   var tempa = lista
   // Traverse all nodes of list A
   while (tempa != null)      {
      var tempb = listb
      var tempc = listc
      // Using two pointer approach for the listb and listc 
      while (tempb != null && tempc!=null)          {
         var current_sum = tempb.value + tempc.value + tempa.value;
         if (current_sum == k){
            console.log("Triplet found: " + tempa.value + " " + tempb.value + " " + tempc.value);
            return true;
         }
         // If the current sum is smaller then look for a greater value of b
         else if (current_sum < k)
         tempb = tempb.next;
         else
         tempc = tempc.next;
      }
      tempa = tempa.next;
   }
   console.log("No Triplet found in the given lists");
   return false;
}
// push function to create the linked list 
function push(head,data){
   let new_node = new Node(data);
   new_node.next = (head);
   (head) = new_node;
   return head;
}
// creating an unsorted linked list 
let head_A =null;
head_A = push (head_A, 2)
head_A = push (head_A, 4)
head_A = push (head_A, 1)
head_A = push (head_A, 8)
   
// create a sorted linked list b consisting of  4 10 15 20
let head_B = null;
head_B = push (head_B, 20)
head_B = push (head_B, 15)
head_B = push (head_B, 10)
head_B = push (head_B, 4)
   
// create another sorted list in descending order 10 9 4 2 
let head_C = null;
head_C = push (head_C, 2)
head_C = push (head_C, 4)
head_C = push (head_C, 9)
head_C = push (head_C, 10)
   
//given number 
var k = 25
// calling the function 
fun(head_A, head_B, head_C, k)

時間和空間複雜度

上述方法的時間複雜度為 O(N*N)，其中 N 是連結串列的大小，因為我們正在遍歷第一個連結串列，這將花費 N 次迭代，並且在每次迭代中，我們都應用雙指標方法，這將花費 O(N)。

我們沒有使用任何額外的空間，這意味著上述程式碼的空間複雜度為 O(1)。

結論

在本文中，我們實現了一個 JavaScript 程式，用於從三個連結串列中找到一個三元組，其和等於給定的數字。這個問題是標準且著名的三數之和問題的變體，但它以連結串列的方式呈現。上述方法的時間複雜度為 O(N*N)，其中 N 是連結串列的大小，空間複雜度為 O(1)。