# Triplet from three linked lists with given sum

Table of Contents

## 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;
if(*head == 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
*head=curr;
}

//O(1) constant time
}

//display linked list
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;
}

void TripletSum(struct LLNode *headList1,struct LLNode *headList2,struct LLNode *headList3,int Input_sum)
{
//Traverse Linked Lists
struct LLNode *List1 = headList1;
while (List1 != NULL)
{
struct LLNode *List2 = headList2;
struct LLNode *List3 = headList3;
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
struct LLNode* headList1 = NULL;
insertAtBeginning(&headList1, 19);
insertAtBeginning(&headList1, 13);
insertAtBeginning(&headList1, 7);

//sorted List2 in ascending order
struct LLNode* headList2 = NULL;
insertAtBeginning(&headList2, 18);
insertAtBeginning(&headList2, 14);
insertAtBeginning(&headList2, 6);

//sorted List3 in descending order
struct LLNode* headList3 = NULL;
insertAtBeginning(&headList3, 4);
insertAtBeginning(&headList3, 9);
insertAtBeginning(&headList3, 21);

cout<<"List1: ";
display(&headList1);
cout<<"List2: ";
display(&headList2);
cout<<"List3: ";
display(&headList3);
int Input_sum = 25;
cout<<"Output: "<<endl;
TripletSum(headList1,headList2,headList3,Input_sum);
return 0;
}```

See also
Reverse a linked list