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;    
    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;
}

 

Translate »