从三个链表中查找和等于给定数字的三元组的 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)。