Linked List: Find 3 nodes whose sum equal to a given number

Problem Statement:

You are given 3 linked list and a number.

You need to find 3 number, one from each list.

1 -> 2 -> 3
5 -> 6 -> 7
8 -> 9 -> 4

M  = 12 

1 + 7 + 4 = 12

Solution 1: Naive Approach

Simple solution is to use 3 loops.

Pick one element from List a, middle loop picks an element from List b, innermost loop picks from list c.

THen check if all the node value adds to the value M. The time complexity will be O(n^3).

Time Complexity: O(n^3)
Space Complexity: O(1)

Solution 2: Efficient Process

1. Sort list b in ascending order and list c in descnding order.

2. Once they are sorted, pick one element at list a and find other 2 by traversing both b and c.

Time Complexity: O(n^2)
Space Complexity: O(1)

Code Solution

#include <iostream> 
using namespace std;

class Node 
{ 
    public:
    int data; 
    Node *next;

    Node (int new_value)
    {
        data = new_value;
        next = nullptr;
    }
}; 

// we assume that all the 3 list are sorted according to the given conditions

void solution(Node *headA, Node *headB, 
                Node *headC, int M) 
{ 
    Node *a = headA; 
 
    while (a != NULL) 
    { 
        Node *b = headB; 
        Node *c = headC; 

        while (b != NULL && c != NULL) 
        { 

            int sum = a->data + b->data + c->data; 
            if (sum == M) 
            { 
            	cout << "Triplet Found: " << a->data << " " << 
                                b->data << " " << c->data; 
                                return;
            } 
 
            else if (sum < M) 
                b = b->next; 
            else 
                c = c->next; 
        } 
        a = a->next; 
    } 
 
    cout << "No such triplet"; 
    return;
} 

int main() 
{ 

    // Created linked list will be 1 -> 2 -> 3 
    Node *headA = new Node(1); 
    headA->next = new Node(2);
    headA->next->next = new Node(3);

    // Created linked list will be 5 -> 6 -> 7 
    Node *headB = new Node(5); 
    headB->next = new Node(6);
    headB->next->next = new Node(7);

    // Created linked list will be 9 -> 8 -> 4  
    Node *headC = new Node(9); 
    headC->next = new Node(8);
    headC->next->next = new Node(4);

    int M = 12;

    solution(headA, headB, headC, M);
    
    return 0; 
} 

Output

Triplet Found: 1 7 4