A function to check if there exist a triplet in three given linked list such that the tripplet's sum is equal to a given number
Let there be 3 linked list a , b , c .
1 Sort list b in ascendinng and c and descending order respectively
2 For each node in list a ,check if there exist a triplet traversing list b and c as shown in function below.
The technique is called Quadratic algorithm for 3 sum problem
Function assumes list b and c already satisfies 1st step and all list are of same length
#include<iostream>
using namespace std;
struct node {
int data;
struct node * next;
};
bool isTripletPresent(struct node* aHead, struct node* bHead, struct node* cHead, int num)
{
struct node* a = aHead;
while (a != NULL)
{
struct node* b = bHead;
struct node* c = cHead;
while (b != NULL && c != NULL)
{
int sum = a->data + b->data + c->data;
if (sum == num)
{
cout << "Found";
return true;
}
else if (sum < num)
{
//look for greater value in b
b = b->next;
}
else {
//look for smaller value in c
c = c->next;
}
}
a = a->next;
}
cout << "No such triplet ";
return false;
}
No comments:
Post a Comment