Find a triplet from three linked lists with sum equal to a given number??

Question

Say you are given

int a[ ] = {1,2,3,4};
int b[ ] = {4,3,2,1};
int S = 5;

Now the task is to find all pairs of two number which adds up to S (One number from a and other number from b).

Answer 1

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)