# Triplet from three linked lists with given sum

## 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.

## 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: ";