JavaScript 从三个链表中找到一个和等于给定数字的三元组

在本文中，我们将实现一个JavaScript程序，从三个链表中找到一个和等于给定数字的三元组。这个问题是标准和著名的三数和问题的一种变体，但以链表的方式表达。让我们看看问题并根据问题的关键点来实现它的代码。

问题介绍

这个问题是三数和问题的一个变异，我们被给定三个数组，我们必须找出数组中是否存在一个三元组，其和恰好等于给定的数字。

在这个问题中，我们被给定三个链表和一个数字，我们必须从所有的链表中选择恰好一个元素，并且选择的数字的和必须等于给定的数字。

如果选择的数字的总和等于给定的数字，则我们必须返回yes，否则返回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是链表的大小。

与第三个链表类似，我们可以对其进行排序并将其反转，使其成为严格递减的链表，这也需要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)