Find a triplet from three Linked Lists with a sum equal to a given number

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>

You can also try this code with Online C++ Compiler

Run Code

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);
    }
}

You can also try this code with Online Java Compiler

Run Code

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.

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Ninja, have a great time learning.