One Possible Solution:----O(n^2)
We have to find a + b + c = SUM where a from first list , b from second list, c from third list
Sort the first Link List in increasing order and second in decreasing order using Merge sort
tmp=thirdList->start
while ( tmp != NULL ) {
c = tmp->data
toFind=SUM - c
t1=firstList->start
t2=secondList->start
while ( t1 != NULL && t2 != NULL){
a= t1->data, b= t2->data
if( a + b < toFind )
t1=t1->next
else if (a + b > toFind)
t2=t2->next
else{ // a + b ==toFind
printf ( " %d %d %d ", a ,b ,c ) // the triplets found
return
}
}
tmp=tmp->next
}
print (" Not Found")
Time Complexity-
Assumption- N- length of First list, M- length of second list, L-length of third list
O(NlogN) + O(MlogM) + O( L * ( M + N)) = O(n^2)