This article will teach to solve a question where three separate linked lists and an integer will be provided as input. Now we need to see if there is a triplet (one from each list) that equals the specified integer.

If we're given three linked lists: 3 ->8 ->1 ->5 ->NULL, 6 ->2 ->8 ->NULL, and 11 ->4 ->2 ->NULL, and the target = 14. Then, using the problem statement as a guide:

We must discover three Nodes (one from each list) that add up to 14 in total.

If we take eight from the first list, two from the second list, and four from the third list, we will get the sum of target=14.

We have grasped the problem statement at this point. Now we'll try to come up with a solution to this difficulty.

Consider how you can address this challenge before continuing to the strategy section.

If you get stuck, don't worry; we'll go over how to solve the problem in detail in the next part.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

1st Approach

The first basic technique that springs to mind is to pick a node from the top of the list. Then we select a node from the second list for each node from the first list, and for each node from the second list selected, we select a node from the third list, and we verify whether the sum of the three nodes selected equals the target or not. We have our necessary triplet if the sum equals the aim.

Time Complexity:

O(N^3) Where N stands for the length of the Linked list.

Reason: Here we are using three continuous nested loops so, the running time of this algorithm is cubic i.e O(N^ 3)

Auxiliary Space Complexity

O(1) As the Linked list data structure is used.

Reason- Here we have used a pre-defined data structure from the collection. As a function of input attributes, the amount of memory space required to solve an instance of the computational problem is set to one.

Although the above method yields the proper outcome, it is time for Complexity. Is it possible to lower the time complexity? Let's see if we can do it with the following strategy.

2nd Approach

To begin, we must sort the second and third lists (the second in ascending order and the third in descending order) to determine if moving forward or backward in the lists will raise or decrease the sum.

Now we must fix a node in the first list and follow the instructions below for each node.

Calculate the total of all three-pointers on each list in various positions.

If the total exceeds the target, we must reduce the total, which requires us to proceed to the third list.

Else If our total is less than the target, we must proceed to the second list to increase our total (as the second list is sorted in ascending order).

If the sums are equal, we can easily print the triplet and demonstrate that one triplet was found in each of the three lists.

C++ Implementation

#include<bits stdc++.h="">
using namespace std;
class Node{
public:
int val;
Node* next;
Node(int d){
val = d;
next = NULL;
}
};
void sortSum(Node *start, Node *scnd,Node *third, int tgt)
{
Node *aa = start;
while (aa != NULL)
{
Node *bb = scnd;
Node *cc = third;
while (bb != NULL && cc != NULL)
{
int totalSum = aa->val + bb->val + cc->val;
if (totalSum == tgt)
{
cout << "Triplet detected: " << aa->val << " " <<bb->val << " " << cc->val;
return;
}
else if (totalSum < tgt)
bb = bb->next;
else
cc = cc->next;
}
aa = aa->next;
}
cout << "No triplet found";
return;
}
int main(void){
Node* start = NULL;
startt = new Node(3);
start->next = new Node(8);
start->next->next = new Node(1);
Node* scnd = NULL;
scnd = new Node(2);
scnd->next = new Node(6);
scnd->next->next = new Node(8);
Node* third = NULL;
third = new Node(11);
third->next = new Node(4);
third->next->next = new Node(2);
sortSum(start,scnd,third,14);
}
</b-></bits>

Java Implementation

class TripletClass
{
Node head;
class Node{
int val;
Node next;
Node (int d) {
val = d; next = null ;
}
}
boolean sortSum(TripletClass llista, TripletClass llistb, TripletClass llistc,int givenNumber)
{
Node a = llista.head;
while (a != null)
{
Node b = llistb.head;
Node c = llistc.head;
while (b != null && c!=null)
{
int totalSum = a.val + b.val + c.val;
if (totalSum == givenNumber)
{
System.out.println("TripletClass found " + a.val +" " + b.val + " " + c.val);
return true;
}
else if (totalSum < givenNumber)
b = b.next;
else
c = c.next;
}
a = a.next;
}
System.out.println("No TripletClass found");
return false;
}
void push(int new_val)
{
Node new_node = new Node(new_val);
new_node.next = head;
head = new_node;
}
public static void main(String args[])
{
TripletClass llista = new TripletClass();
TripletClass llistb = new TripletClass();
TripletClass llistc = new TripletClass();
llista.push(3);
llista.push(8);
llista.push(1);
llistb.push(2);
llistb.push(6);
llistb.push(8);
llistc.push(11);
llistc.push(4);
llistc.push(2);
int givenNumber = 14;
llista.sortSum(llista,llistb,llistc,givenNumber);
}
}

Output

Triplet detected: 8 2 4

Time Complexity:

O(N ^ 2), Where ‘N’ stands for the length of the linked list.

Reason: As we are using a nested loop so the time complexity would be O(N) * O(N) ~ O(N^ N)

Auxiliary Space Complexity

O(1)

Reason- Here we have used a pre-defined data structure from the collection. As a function of input attributes, the amount of memory space required to solve an instance of the computational problem is set to one.

Frequently Asked Questions

What's the difference between a linked list and an array?

An array is a group of elements with the same data type. A linked list is an ordered collection of elements of the same type, each of which is linked to the next via pointers. The array index can be used to access entries in an array at random. Linked lists do not allow for random access.

Is it true that a linked list is a static data structure?

The primary distinction between arrays and linked lists is that arrays are static data structures, whereas linked lists are dynamic.

In a binary search tree, what is the difficulty of deletion?

Time complexity is O in general (h). The deletion of element 1 necessitates a traversal of all elements to locate it (in orders 3, 2, 1). As a result, deletion in a binary tree has an O worst-case complexity (n). Time complexity is O in general (h).

In DSA, what is the AVL tree?

A binary search tree in which the height difference between each node’s left and right subtrees is less than or equal to one is known as an AVL tree. Adelson, Velskii, and Landi discovered the approach for balancing the height of binary trees, which is known as the AVL tree or Balanced Binary Tree.

Is the linked list ordered?

Linked Lists, like stacks and queues, are a type of sequential collection. It doesn't have to be in any particular order. A linked list is a collection of independent nodes that can hold any type of data. Each node in the link has a reference to the next node.

Conclusion

This article has gone through Deleting Node in Different Situations, Removing an element from the list's beginning. The list is displayed in its entirety. Searches for an element using the specified key. Check out our articles in Library. You may also CheckOut our course on the linked list.