### Problem Statement

We will be given three different linked lists and an integer as input. Now, we need to find whether there is a triplet (one from each list) that sums up to the given integer.

### Problem Statement Understanding

To understand the problem statement, let us take examples.

If the linked lists given to us are 3â†’8â†’1â†’5â†’NULL, 6â†’2â†’8â†’NULL, and 11â†’4â†’2â†’NULL, and the target = 14. Then, according to the problem statement:

- We need to find three Nodes (one from each list) such that they sum up to 14.
- If we select
**8**from the**first list**,**2**from the**second list**and**4**from the**third list**, we will get the sum equal to the**target=14**. - The required triplet will be
**(8,2,4)**.

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

Before moving to the approach section, try to think about how you can approach this problem.

- If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Letâ€™s move to the approach section.

### Approach 1

The naive approach that comes to our mind is to first select a node from the first list. Then for each node of the first list, we select a node from the second list, and for each selected node of the second list, we select a node in the third list, and then we check if the sum of the 3 nodes selected is equal to target or not. If the sum is equal to the target, we have our required triplet.

**Time Complexity:** O(n^{3}) , n is the number of nodes in a list.

The above approach gives the correct result, but its time complexity is high. Can we reduce the time complexity? Let us find out If we can do so in the below approach.

### Approach 2

- First, we need to sort the second and third lists (the second list will be sorted in ascending order and the third list in descending order), so that we could be sure whether moving forward or backward in the lists is going to increase or decrease the sum.
- Now, we need to fix a node in the first list and for each node, we need to perform the below steps.
- Calculate the sum of all three-pointers present at different positions on each list.
- If the sum is greater than the target, then we need to decrease the sum, so we need to move forward in the third list (if you visualize carefully, you can see that moving forward in the third list will decrease the sum, because the third list is sorted in descending order).
- Else If the sum is smaller than the target, we need to move forward in the second list to increase our sum (as the second list is sorted in ascending order).
- If the sum is equal, then we can easily print the triplet and show that we have found one triplet in the three given lists.

To see the above approach in more detail, move to the algorithm section.

### Algorithm

1) First, sort the second list in ascending order and the third list in descending order.

2) Initialize a pointer **a** with head of **first list**.

3) Run a while loop till **a** is not NULL and inside the loop:

- Initialize pointer
**b**and**c**with**head of second and third list**, respectively. - Run a while loop till
**b**and**c**are not NULL.- Initialize variable
**sum**as the sum of values pointed by pointers**a**,**b**, and**c**. - If the
**sum**is equal to the**target**, print the values pointed by**a**,**b**, and**c**and return from the function. - If the
**sum**is less than the**target**, move forward**b**by one node. Else, move forward**c**by one node.

- Initialize variable
- Move forward
**a**by one node.

**Note:** For simplicity, in dry run and code implementation, we took second and third linked lists, which are already sorted in ascending and descending order, respectively. If you want to know how to sort a linked list, please feel free to refer to this article for sorting related concepts of linked list. Also, inside the code implementation, we haven’t provided the sorting function (function to sort the linked list); if you want to take unsorted linked lists, please sort them in proper format (the second list will be sorted in ascending order and the third list in descending order) using code from above-mentioned article, before passing them to **isSumSorted()** function in the code.

### Dry Run

### Code Implementation

#include<stdio.h> #include<stdlib.h> #include<stdbool.h> /* Link list node */ struct Node { int data; struct Node* next; }; void isSumSorted(struct Node *first,struct Node *second,struct Node *third, int target) { struct Node *a = first; //Select a node in first list and //traverse the other two lists for //each selected node while (a != NULL) { struct Node *b = second; struct Node *c = third; //select posssible pairs of nodes //from second and thirs list //(one from each list) while (b != NULL && c != NULL) { // if sum is equal to our target int sum = a->data + b->data + c->data; if (sum == target) { printf ("Triplet Found: %d %d %d ", a->data, b->data, c->data); return; } // If sum is less than target else if (sum < target) b = b->next; else c = c->next; } a = a->next; // Move ahead in list a } printf( "No such triplet"); return; } struct Node* newNode(int x) { struct Node* node = malloc(sizeof(struct Node*)); node->data = x; node->next = NULL; return node; } int main(void){ struct Node* first = NULL; first = newNode(3); first->next = newNode(8); first->next->next = newNode(1); struct Node* second = NULL; second = newNode(2); second->next = newNode(6); second->next->next = newNode(8); struct Node* third = NULL; third = newNode(11); third->next = newNode(4); third->next->next = newNode(2); isSumSorted(first,second,third,14); }

#include<bits stdc++.h=""> using namespace std; class Node{ public: int data; Node* next; Node(int x){ data = x; next = NULL; } }; void isSumSorted(Node *first, Node *second,Node *third, int target) { Node *a = first; //Select a node in first list and //traverse the other two lists for //each selected node while (a != NULL) { Node *b = second; Node *c = third; //select posssible pairs of nodes //from second and thirs list //(one from each list) while (b != NULL && c != NULL) { // if sum is equal to our target int sum = a->data + b->data + c->data; if (sum == target) { cout << "Triplet Found: " << a->data << " " <<b->data << " " << c->data; return; } // If sum is less than target else if (sum < target) b = b->next; else c = c->next; } a = a->next; // Move ahead in list a } cout << "No such triplet"; return; } int main(void){ Node* first = NULL; first = new Node(3); first->next = new Node(8); first->next->next = new Node(1); Node* second = NULL; second = new Node(2); second->next = new Node(6); second->next->next = new Node(8); Node* third = NULL; third = new Node(11); third->next = new Node(4); third->next->next = new Node(2); isSumSorted(first,second,third,14); }

class Triplet { Node head; class Node { int data; Node next; Node(int d) {data = d; next = null; } } boolean isSumSorted(Triplet llist1, Triplet llist2, Triplet llist3,int givenNumber) { Node a = llist1.head; while (a != null) { Node b = llist2.head; Node c = llist3.head; // for every node in la pick 2 nodes from lb and lc while (b != null && c!=null) { int sum = a.data + b.data + c.data; if (sum == givenNumber) { System.out.println("Triplet found " + a.data +" " + b.data + " " + c.data); return true; } // If sum is smaller then look for greater value of b else if (sum < givenNumber) b = b.next; else c = c.next; } a = a.next; } System.out.println("No Triplet found"); return false; } void push(int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } public static void main(String args[]) { Triplet llist1 = new Triplet(); Triplet llist2 = new Triplet(); Triplet llist3 = new Triplet(); /* Create Linked List llist1 100->15->5->20 */ llist1.push(3); llist1.push(8); llist1.push(1); /*create a sorted linked list 'b' 2->4->9->10 */ llist2.push(2); llist2.push(6); llist2.push(8); /*create another sorted linked list 'c' 8->4->2->1 */ llist3.push(11); llist3.push(4); llist3.push(2); int givenNumber = 14; llist1.isSumSorted(llist1,llist2,llist3,givenNumber); } }

class Node: def __init__(self, new_data): self.data = new_data self.next = None def push ( head_ref, new_data) : new_node = Node(0) new_node.data = new_data new_node.next = (head_ref) (head_ref) = new_node return head_ref def isSumSorted(headA, headB,headC, givenNumber) : a = headA while (a != None) : b = headB c = headC while (b != None and c != None) : sum = a.data + b.data + c.data if (sum == givenNumber) : print("Triplet Found:" , a.data , b.data , c.data) return True elif (sum < givenNumber): b = b.next else : c = c.next a = a.next print("No such triplet") return False headA = None headB = None headC = None headA = push (headA, 20) headA = push (headA, 4) headA = push (headA, 15) headA = push (headA, 10) headB = push (headB, 10) headB = push (headB, 9) headB = push (headB, 4) headB = push (headB, 2) headC = push (headC, 1) headC = push (headC, 2) headC = push (headC, 4) headC = push (headC, 8) givenNumber = 15 isSumSorted (headA, headB, headC, givenNumber)

#### Output

Triplet Found: 8 2 4

**Time Complexity:** O(n^{2}) ,n is the number of nodes in the list.

[forminator_quiz id=”5843″]

So, in this blog, we have tried to explain how you can Find a triplet from three linked lists with a sum equal to a given number most optimally. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.