Home » Technical Interview Questions » LinkedList Interview Questions » Triplet from three linked lists with given sum

# Triplet from three linked lists with given sum

## In the given three linked lists, find one node from each of the three lists such that there sum is equal to given value.

### Example ## Algorithm

a. Sort List1 in ascending order.

b. Sort List2 in descending order.

c. Traverse in the linked lists, pick first element in List1 and for every element in List1 pick a pair of elements in List2 and List3.

d. If sum of the elements is equal to given number print them.

e. If sum is less than given number move position in List2.

f. If sum is greater than given number move position in List3.

### Algorithm working  ## C++ Program

```#include <bits/stdc++.h>

using namespace std;

struct LLNode
{
int data;
struct LLNode* next;
};

/* Function to insertAtBeginning List1 node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
struct LLNode* curr = new LLNode;
curr->data = dataToBeInserted;
curr->next = NULL;
*head=curr; //if this is first node make this as head of list

else
{
curr->next=*head; //else make the curr (new) node's next point to head and make this new node List1 the head
}

//O(1) constant time
}

void display(struct LLNode**node)
{
struct LLNode *temp= *node;
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

{
while (List1 != NULL)
{
while (List2 != NULL && List3 != NULL)
{
int sum = List1->data + List2->data + List3->data;
//If sum is equal to given number
//print the triplet
if (sum == Input_sum)
{
cout<<"Triplet is: "<<List1->data<<", "<<List2->data<<", "<<List3->data;
return;
}
//If sum is less than given number.
//move in List2
else if (sum < Input_sum)
{
List2 = List2->next;
}
//If sum is greater than given number.
//move in List3
else
{
List3 = List3->next;
}
}
List1 = List1->next;
}
cout<<"No triplet found!";
return;
}

//Main function
int main()
{
//List1

//sorted List2 in ascending order

//sorted List3 in descending order

cout<<"List1: ";
cout<<"List2: ";