Skip to main content

Find a triplet from three linked lists with given sum

Find a pair with the given sum in three unsorted linked list. This pair must contain at least one element of all linked lists.

Example
----------
    List  A    5 → 2 → -2 → 1 → 3 → 6 → NULL
    List  B   -1 → 2 → 5 → 4 → 9 → -9 → NULL
    List  C    1 → 2 → 8 → 4 → 3 → 6 → NULL
    -----------------------------------------
    Sum : 22

    List  A    5 → 2 → -2 → 1 → 3 → 6 → NULL
               ↑
    List  B   -1 → 2 → 5 → 4 → 9 → -9 → NULL
                               ↑
    List  C    1 → 2 → 8 → 4 → 3 → 6 → NULL
                       ↑
    Triplet :  (5,9,8)

We can solve this problem by traversal of the linked list. Print a valid message when the valid list does not contain totals. Here given code implementation process.

/*
    C program for
    Find a triplet from three linked lists with given sum
*/
#include <stdio.h>
#include <stdlib.h>

// Linked List LinkNode
struct LinkNode
{
	int data;
	struct LinkNode *next;
};
// Singly linked list 
struct SingleLL
{
	struct LinkNode *head;
	struct LinkNode *tail;
};
// Returns the new linked list
struct SingleLL *newLinkedList()
{
	// Create memory of head and tail Nodes
	struct SingleLL *sll = 
      (struct SingleLL *) malloc(sizeof(struct SingleLL));
	if (sll == NULL)
	{
		printf("Memory overflow\n");
	}
	else
	{
		sll->head = NULL;
	}
	return sll;
}
// Handles the request of adding new node in linked list
void addNode(struct SingleLL *sll, int data)
{
	// Create dynamic node
	struct LinkNode *node = 
      (struct LinkNode *) malloc(sizeof(struct LinkNode));
	if (node == NULL)
	{
		printf("Memory overflow to Create LinkNode\n");
		return;
	}
	else
	{
		// Set initial node value
		node->data = data;
		node->next = NULL;
	}
	if (sll->head == NULL)
	{
		sll->head = node;
	}
	else
	{
		sll->tail->next = node;
	}
	sll->tail = node;
}
// Display linked list element
void display(struct LinkNode *node)
{
	if (node == NULL)
	{
		return;
	}
	struct LinkNode *temp = node;
	// iterating linked list elements
	while (temp != NULL)
	{
		printf(" %d →", temp->data);
		// Visit to next node
		temp = temp->next;
	}
	printf(" NULL\n");
}
void tripletOfSumK(struct LinkNode *l1, 
                   struct LinkNode *l2, 
                   struct LinkNode *l3, int k)
{
	if (l1 == NULL || l2 == NULL || l3 == NULL)
	{
		printf(" Given Sum triplet not exist [Case Empty List]\n");
		return;
	}
	printf("\n Given Lists \n");
	display(l1);
	display(l2);
	display(l3);
	printf(" Sum : %d \n", k);
	struct LinkNode *t1 = l1;
	struct LinkNode *t2 = l2;
	struct LinkNode *t3 = l3;
	// Compare linked list node
	while (t1 != NULL)
	{
		while (t2 != NULL)
		{
			while (t3 != NULL)
			{
				if (t1->data + t2->data + t3->data == k)
				{
					printf(" Triplet :  (%d,%d,%d)", 
                           t1->data, t2->data, t3->data);
					return;
				}
				// Visit to next node
				t3 = t3->next;
			}
			// Visit to next node
			t2 = t2->next;
			t3 = l3;
		}
		// Visit to next node
		t1 = t1->next;
		t2 = l2;
	}
	printf(" Triplet of sum %d not found \n", k);
}
int main(int argc, char
	const *argv[])
{
	struct SingleLL *sll1 = newLinkedList();
	struct SingleLL *sll2 = newLinkedList();
	struct SingleLL *sll3 = newLinkedList();
	// First linked list
	//  5 → 2 → -2 → 1 → 3 → 6 → NULL
	addNode(sll1, 5);
	addNode(sll1, 2);
	addNode(sll1, -2);
	addNode(sll1, 1);
	addNode(sll1, 3);
	addNode(sll1, 6);
	// Second linked list
	//  -1 → 2 → 5 → 4 → 9 → -9 → NULL
	addNode(sll2, -1);
	addNode(sll2, 2);
	addNode(sll2, 5);
	addNode(sll2, 4);
	addNode(sll2, 9);
	addNode(sll2, -9);
	// Third linked list
	//  1 → 2 → 8 → 4 → 3 → 6 → NULL
	addNode(sll3, 1);
	addNode(sll3, 2);
	addNode(sll3, 8);
	addNode(sll3, 4);
	addNode(sll3, 3);
	addNode(sll3, 6);
	int k = 22;
	// Test 
	tripletOfSumK(sll1->head, sll2->head, sll3->head, k);
	return 0;
}

Output

 Given Lists
 5 → 2 → -2 → 1 → 3 → 6 → NULL
 -1 → 2 → 5 → 4 → 9 → -9 → NULL
 1 → 2 → 8 → 4 → 3 → 6 → NULL
 Sum : 22
 Triplet :  (5,9,8)
/*
    Java program for
    Find a triplet from three linked lists with given sum
*/
// Linked list node
class LinkNode
{
    public int data;
    public LinkNode next;
    public LinkNode(int data)
    {
        this.data = data;
        this.next = null;
    }
}
public class SingleLL
{
    public LinkNode head;
    public LinkNode tail;
    public SingleLL()
    {
        this.head = null;
        this.tail = null;
    }
    // Add new Node at end of linked list 
    public void addNode(int data)
    {
        LinkNode node = new LinkNode(data);
        if (this.head == null)
        {
            this.head = node;
        }
        else
        {
            // Append the node at last position
            this.tail.next = node;
        }
        this.tail = node;
    }
    // Display linked list element
    public void display()
    {
        if (this.head == null)
        {
            return;
        }
        LinkNode temp = this.head;
        // iterating linked list elements
        while (temp != null)
        {
            System.out.print(" " + temp.data + " →");
            // Visit to next node
            temp = temp.next;
        }
        System.out.print(" NULL\n");
    }
    public void tripletOfSumK( SingleLL l2, SingleLL l3, int k)
    {
        if (this.head == null || l2.head == null || l3.head == null)
        {
          	//  [Case Empty List]
            System.out.print(" Given Sum triplet not exist\n");
            return;
        }
        System.out.print("\n Given Lists \n");
        this.display();
        l2.display();
        l3.display();
        System.out.print(" Sum : " + k + " \n");
        LinkNode t1 = this.head;
        LinkNode t2 = l2.head;
        LinkNode t3 = l3.head;
        // Compare linked list node
        while (t1 != null)
        {
            while (t2 != null)
            {
                while (t3 != null)
                {
                    if (t1.data + t2.data + t3.data == k)
                    {
                        System.out.print(" Triplet : (" + 
                            t1.data + "," + t2.data + "," + t3.data + ")");
                        return;
                    }
                    // Visit to next node
                    t3 = t3.next;
                }
                // Visit to next node
                t2 = t2.next;
                t3 = l3.head;
            }
            // Visit to next node
            t1 = t1.next;
            t2 = l2.head;
        }
        System.out.print(" Triplet of sum " + k + " not found \n");
    }
    public static void main(String[] args)
    {
        SingleLL sll1 = new SingleLL();
        SingleLL sll2 = new SingleLL();
        SingleLL sll3 = new SingleLL();


        // First linked list
        //  5 → 2 → -2 → 1 → 3 → 6 → NULL
        sll1.addNode(5);
        sll1.addNode(2);
        sll1.addNode(-2);
        sll1.addNode(1);
        sll1.addNode(3);
        sll1.addNode(6);
        // Second linked list
        //  -1 → 2 → 5 → 4 → 9 → -9 → NULL
        sll2.addNode(-1);
        sll2.addNode(2);
        sll2.addNode(5);
        sll2.addNode(4);
        sll2.addNode(9);
        sll2.addNode(-9);
        // Third linked list
        //  1 → 2 → 8 → 4 → 3 → 6 → NULL
        sll3.addNode(1);
        sll3.addNode(2);
        sll3.addNode(8);
        sll3.addNode(4);
        sll3.addNode(3);
        sll3.addNode(6);
        int k = 22;
        // Test 
        sll1.tripletOfSumK(sll2, sll3, k);
    }
}

Output

 Given Lists
 5 → 2 → -2 → 1 → 3 → 6 → NULL
 -1 → 2 → 5 → 4 → 9 → -9 → NULL
 1 → 2 → 8 → 4 → 3 → 6 → NULL
 Sum : 22
 Triplet : (5,9,8)
// Include header file
#include <iostream>
using namespace std;
/*
    C++ program for
    Find a triplet from three linked lists with given sum
*/
// Linked list node
class LinkNode
{
	public: 
    int data;
	LinkNode *next;
	LinkNode(int data)
	{
		this->data = data;
		this->next = NULL;
	}
};
class SingleLL
{
	public: 
    LinkNode *head;
	LinkNode *tail;
	SingleLL()
	{
		this->head = NULL;
		this->tail = NULL;
	}
	// Add new Node at end of linked list 
	void addNode(int data)
	{
		LinkNode *node = new LinkNode(data);
		if (this->head == NULL)
		{
			this->head = node;
		}
		else
		{
			// Append the node at last position
			this->tail->next = node;
		}
		this->tail = node;
	}
	// Display linked list element
	void display()
	{
		if (this->head == NULL)
		{
			return;
		}
		LinkNode *temp = this->head;
		// iterating linked list elements
		while (temp != NULL)
		{
			cout << " " << temp->data << " →";
			// Visit to next node
			temp = temp->next;
		}
		cout << " NULL\n";
	}
	void tripletOfSumK(SingleLL *l2, 
                       SingleLL *l3, 
                       int k)
	{
		if (this->head == NULL || 
            l2->head == NULL || 
            l3->head == NULL)
		{
			//  [Case Empty List]
			cout << " Given Sum triplet not exist\n";
			return;
		}
		cout << "\n Given Lists \n";
		this->display();
		l2->display();
		l3->display();
		cout << " Sum : " << k << " \n";
		LinkNode *t1 = this->head;
		LinkNode *t2 = l2->head;
		LinkNode *t3 = l3->head;
		// Compare linked list node
		while (t1 != NULL)
		{
			while (t2 != NULL)
			{
				while (t3 != NULL)
				{
					if (t1->data + t2->data + t3->data == k)
					{
						cout << " Triplet : (" 
                      		 << t1->data << "," 
                             << t2->data << "," 
                             << t3->data << ")";
						return;
					}
					// Visit to next node
					t3 = t3->next;
				}
				// Visit to next node
				t2 = t2->next;
				t3 = l3->head;
			}
			// Visit to next node
			t1 = t1->next;
			t2 = l2->head;
		}
		cout << " Triplet of sum " << k << " not found \n";
	}
};
int main()
{
	SingleLL *sll1 = new SingleLL();
	SingleLL *sll2 = new SingleLL();
	SingleLL *sll3 = new SingleLL();
	// First linked list
	//  5 → 2 → -2 → 1 → 3 → 6 → NULL
	sll1->addNode(5);
	sll1->addNode(2);
	sll1->addNode(-2);
	sll1->addNode(1);
	sll1->addNode(3);
	sll1->addNode(6);
	// Second linked list
	//  -1 → 2 → 5 → 4 → 9 → -9 → NULL
	sll2->addNode(-1);
	sll2->addNode(2);
	sll2->addNode(5);
	sll2->addNode(4);
	sll2->addNode(9);
	sll2->addNode(-9);
	// Third linked list
	//  1 → 2 → 8 → 4 → 3 → 6 → NULL
	sll3->addNode(1);
	sll3->addNode(2);
	sll3->addNode(8);
	sll3->addNode(4);
	sll3->addNode(3);
	sll3->addNode(6);
	int k = 22;
	// Test 
	sll1->tripletOfSumK(sll2, sll3, k);
	return 0;
}

Output

 Given Lists
 5 → 2 → -2 → 1 → 3 → 6 → NULL
 -1 → 2 → 5 → 4 → 9 → -9 → NULL
 1 → 2 → 8 → 4 → 3 → 6 → NULL
 Sum : 22
 Triplet : (5,9,8)
// Include namespace system
using System;
/*
    Csharp program for
    Find a triplet from three linked lists with given sum
*/
// Linked list node
public class LinkNode
{
	public int data;
	public LinkNode next;
	public LinkNode(int data)
	{
		this.data = data;
		this.next = null;
	}
}
public class SingleLL
{
	public LinkNode head;
	public LinkNode tail;
	public SingleLL()
	{
		this.head = null;
		this.tail = null;
	}
	// Add new Node at end of linked list 
	public void addNode(int data)
	{
		LinkNode node = new LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail.next = node;
		}
		this.tail = node;
	}
	// Display linked list element
	public void display()
	{
		if (this.head == null)
		{
			return;
		}
		LinkNode temp = this.head;
		// iterating linked list elements
		while (temp != null)
		{
			Console.Write(" " + temp.data + " →");
			// Visit to next node
			temp = temp.next;
		}
		Console.Write(" NULL\n");
	}
	public void tripletOfSumK(SingleLL l2, SingleLL l3, int k)
	{
		if (this.head == null || 
            l2.head == null || 
            l3.head == null)
		{
			//  [Case Empty List]
			Console.Write(" Given Sum triplet not exist\n");
			return;
		}
		Console.Write("\n Given Lists \n");
		this.display();
		l2.display();
		l3.display();
		Console.Write(" Sum : " + k + " \n");
		LinkNode t1 = this.head;
		LinkNode t2 = l2.head;
		LinkNode t3 = l3.head;
		// Compare linked list node
		while (t1 != null)
		{
			while (t2 != null)
			{
				while (t3 != null)
				{
					if (t1.data + t2.data + t3.data == k)
					{
						Console.Write(" Triplet : (" + 
                                      t1.data + "," +
                                      t2.data + "," + 
                                      t3.data + ")");
						return;
					}
					// Visit to next node
					t3 = t3.next;
				}
				// Visit to next node
				t2 = t2.next;
				t3 = l3.head;
			}
			// Visit to next node
			t1 = t1.next;
			t2 = l2.head;
		}
		Console.Write(" Triplet of sum " + k + " not found \n");
	}
	public static void Main(String[] args)
	{
		SingleLL sll1 = new SingleLL();
		SingleLL sll2 = new SingleLL();
		SingleLL sll3 = new SingleLL();
		// First linked list
		//  5 → 2 → -2 → 1 → 3 → 6 → NULL
		sll1.addNode(5);
		sll1.addNode(2);
		sll1.addNode(-2);
		sll1.addNode(1);
		sll1.addNode(3);
		sll1.addNode(6);
		// Second linked list
		//  -1 → 2 → 5 → 4 → 9 → -9 → NULL
		sll2.addNode(-1);
		sll2.addNode(2);
		sll2.addNode(5);
		sll2.addNode(4);
		sll2.addNode(9);
		sll2.addNode(-9);
		// Third linked list
		//  1 → 2 → 8 → 4 → 3 → 6 → NULL
		sll3.addNode(1);
		sll3.addNode(2);
		sll3.addNode(8);
		sll3.addNode(4);
		sll3.addNode(3);
		sll3.addNode(6);
		int k = 22;
		// Test 
		sll1.tripletOfSumK(sll2, sll3, k);
	}
}

Output

 Given Lists
 5 → 2 → -2 → 1 → 3 → 6 → NULL
 -1 → 2 → 5 → 4 → 9 → -9 → NULL
 1 → 2 → 8 → 4 → 3 → 6 → NULL
 Sum : 22
 Triplet : (5,9,8)
package main
import "fmt"
/*
    Go program for
    Find a triplet from three linked lists with given sum
*/
// Linked list node
type LinkNode struct {
	data int
	next * LinkNode
}
func getLinkNode(data int) * LinkNode {
	var me *LinkNode = &LinkNode {}
	me.data = data
	me.next = nil
	return me
}
type SingleLL struct {
	head * LinkNode
	tail * LinkNode
}
func getSingleLL() * SingleLL {
	var me *SingleLL = &SingleLL {}
	me.head = nil
	me.tail = nil
	return me
}
// Add new Node at end of linked list 
func(this *SingleLL) addNode(data int) {
	var node * LinkNode = getLinkNode(data)
	if this.head == nil {
		this.head = node
	} else {
		// Append the node at last position
		this.tail.next = node
	}
	this.tail = node
}
// Display linked list element
func(this SingleLL) display() {
	if this.head == nil {
		return
	}
	var temp * LinkNode = this.head
	// iterating linked list elements
	for (temp != nil) {
		fmt.Print(" ", temp.data, " →")
		// Visit to next node
		temp = temp.next
	}
	fmt.Print(" NULL\n")
}
func(this SingleLL) tripletOfSumK(l2 * SingleLL, 
	l3 * SingleLL, k int) {
	if this.head == nil || l2.head == nil || l3.head == nil {
		//  [Case Empty List]
		fmt.Print(" Given Sum triplet not exist\n")
		return
	}
	fmt.Print("\n Given Lists \n")
	this.display()
	l2.display()
	l3.display()
	fmt.Print(" Sum : ", k, " \n")
	var t1 * LinkNode = this.head
	var t2 * LinkNode = l2.head
	var t3 * LinkNode = l3.head
	// Compare linked list node
	for (t1 != nil) {
		for (t2 != nil) {
			for (t3 != nil) {
				if t1.data + t2.data + t3.data == k {
					fmt.Print(" Triplet : (", 
						t1.data, ",", 
						t2.data, ",", 
						t3.data, ")")
					return
				}
				// Visit to next node
				t3 = t3.next
			}
			// Visit to next node
			t2 = t2.next
			t3 = l3.head
		}
		// Visit to next node
		t1 = t1.next
		t2 = l2.head
	}
	fmt.Print(" Triplet of sum ", k, " not found \n")
}
func main() {
	var sll1 * SingleLL = getSingleLL()
	var sll2 * SingleLL = getSingleLL()
	var sll3 * SingleLL = getSingleLL()
	// First linked list
	//  5 → 2 → -2 → 1 → 3 → 6 → NULL
	sll1.addNode(5)
	sll1.addNode(2)
	sll1.addNode(-2)
	sll1.addNode(1)
	sll1.addNode(3)
	sll1.addNode(6)
	// Second linked list
	//  -1 → 2 → 5 → 4 → 9 → -9 → NULL
	sll2.addNode(-1)
	sll2.addNode(2)
	sll2.addNode(5)
	sll2.addNode(4)
	sll2.addNode(9)
	sll2.addNode(-9)
	// Third linked list
	//  1 → 2 → 8 → 4 → 3 → 6 → NULL
	sll3.addNode(1)
	sll3.addNode(2)
	sll3.addNode(8)
	sll3.addNode(4)
	sll3.addNode(3)
	sll3.addNode(6)
	var k int = 22
	// Test 
	sll1.tripletOfSumK(sll2, sll3, k)
}

Output

 Given Lists
 5 → 2 → -2 → 1 → 3 → 6 → NULL
 -1 → 2 → 5 → 4 → 9 → -9 → NULL
 1 → 2 → 8 → 4 → 3 → 6 → NULL
 Sum : 22
 Triplet : (5,9,8)
<?php
/*
    Php program for
    Find a triplet from three linked lists with given sum
*/
// Linked list node
class LinkNode
{
	public $data;
	public $next;
	public	function __construct($data)
	{
		$this->data = $data;
		$this->next = NULL;
	}
}
class SingleLL
{
	public $head;
	public $tail;
	public	function __construct()
	{
		$this->head = NULL;
		$this->tail = NULL;
	}
	// Add new Node at end of linked list 
	public	function addNode($data)
	{
		$node = new LinkNode($data);
		if ($this->head == NULL)
		{
			$this->head = $node;
		}
		else
		{
			// Append the node at last position
			$this->tail->next = $node;
		}
		$this->tail = $node;
	}
	// Display linked list element
	public	function display()
	{
		if ($this->head == NULL)
		{
			return;
		}
		$temp = $this->head;
		// iterating linked list elements
		while ($temp != NULL)
		{
			echo(" ".$temp->data.
				" →");
			// Visit to next node
			$temp = $temp->next;
		}
		echo(" NULL\n");
	}
	public	function tripletOfSumK($l2, $l3, $k)
	{
		if ($this->head == NULL || 
            $l2->head == NULL || 
            $l3->head == NULL)
		{
			//  [Case Empty List]
			echo(" Given Sum triplet not exist\n");
			return;
		}
		echo("\n Given Lists \n");
		$this->display();
		$l2->display();
		$l3->display();
		echo(" Sum : ".$k.
			" \n");
		$t1 = $this->head;
		$t2 = $l2->head;
		$t3 = $l3->head;
		// Compare linked list node
		while ($t1 != NULL)
		{
			while ($t2 != NULL)
			{
				while ($t3 != NULL)
				{
					if ($t1->data + $t2->data + $t3->data == $k)
					{
						echo(" Triplet : (".$t1->data.
							",".$t2->data.
							",".$t3->data.
							")");
						return;
					}
					// Visit to next node
					$t3 = $t3->next;
				}
				// Visit to next node
				$t2 = $t2->next;
				$t3 = $l3->head;
			}
			// Visit to next node
			$t1 = $t1->next;
			$t2 = $l2->head;
		}
		echo(" Triplet of sum ".$k.
			" not found \n");
	}
}

function main()
{
	$sll1 = new SingleLL();
	$sll2 = new SingleLL();
	$sll3 = new SingleLL();
	// First linked list
	//  5 → 2 → -2 → 1 → 3 → 6 → NULL
	$sll1->addNode(5);
	$sll1->addNode(2);
	$sll1->addNode(-2);
	$sll1->addNode(1);
	$sll1->addNode(3);
	$sll1->addNode(6);
	// Second linked list
	//  -1 → 2 → 5 → 4 → 9 → -9 → NULL
	$sll2->addNode(-1);
	$sll2->addNode(2);
	$sll2->addNode(5);
	$sll2->addNode(4);
	$sll2->addNode(9);
	$sll2->addNode(-9);
	// Third linked list
	//  1 → 2 → 8 → 4 → 3 → 6 → NULL
	$sll3->addNode(1);
	$sll3->addNode(2);
	$sll3->addNode(8);
	$sll3->addNode(4);
	$sll3->addNode(3);
	$sll3->addNode(6);
	$k = 22;
	// Test 
	$sll1->tripletOfSumK($sll2, $sll3, $k);
}
main();

Output

 Given Lists
 5 → 2 → -2 → 1 → 3 → 6 → NULL
 -1 → 2 → 5 → 4 → 9 → -9 → NULL
 1 → 2 → 8 → 4 → 3 → 6 → NULL
 Sum : 22
 Triplet : (5,9,8)
/*
    Node JS program for
    Find a triplet from three linked lists with given sum
*/
// Linked list node
class LinkNode
{
	constructor(data)
	{
		this.data = data;
		this.next = null;
	}
}
class SingleLL
{
	constructor()
	{
		this.head = null;
		this.tail = null;
	}
	// Add new Node at end of linked list 
	addNode(data)
	{
		var node = new LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail.next = node;
		}
		this.tail = node;
	}
	// Display linked list element
	display()
	{
		if (this.head == null)
		{
			return;
		}
		var temp = this.head;
		// iterating linked list elements
		while (temp != null)
		{
			process.stdout.write(" " + temp.data + " →");
			// Visit to next node
			temp = temp.next;
		}
		process.stdout.write(" NULL\n");
	}
	tripletOfSumK(l2, l3, k)
	{
		if (this.head == null || l2.head == null || l3.head == null)
		{
			//  [Case Empty List]
			process.stdout.write(" Given Sum triplet not exist\n");
			return;
		}
		process.stdout.write("\n Given Lists \n");
		this.display();
		l2.display();
		l3.display();
		process.stdout.write(" Sum : " + k + " \n");
		var t1 = this.head;
		var t2 = l2.head;
		var t3 = l3.head;
		// Compare linked list node
		while (t1 != null)
		{
			while (t2 != null)
			{
				while (t3 != null)
				{
					if (t1.data + t2.data + t3.data == k)
					{
						process.stdout.write(" Triplet : (" + 
                                             t1.data + "," + 
                                             t2.data + "," + 
                                             t3.data + ")");
						return;
					}
					// Visit to next node
					t3 = t3.next;
				}
				// Visit to next node
				t2 = t2.next;
				t3 = l3.head;
			}
			// Visit to next node
			t1 = t1.next;
			t2 = l2.head;
		}
		process.stdout.write(" Triplet of sum " + k + " not found \n");
	}
}

function main()
{
	var sll1 = new SingleLL();
	var sll2 = new SingleLL();
	var sll3 = new SingleLL();
	// First linked list
	//  5 → 2 → -2 → 1 → 3 → 6 → NULL
	sll1.addNode(5);
	sll1.addNode(2);
	sll1.addNode(-2);
	sll1.addNode(1);
	sll1.addNode(3);
	sll1.addNode(6);
	// Second linked list
	//  -1 → 2 → 5 → 4 → 9 → -9 → NULL
	sll2.addNode(-1);
	sll2.addNode(2);
	sll2.addNode(5);
	sll2.addNode(4);
	sll2.addNode(9);
	sll2.addNode(-9);
	// Third linked list
	//  1 → 2 → 8 → 4 → 3 → 6 → NULL
	sll3.addNode(1);
	sll3.addNode(2);
	sll3.addNode(8);
	sll3.addNode(4);
	sll3.addNode(3);
	sll3.addNode(6);
	var k = 22;
	// Test 
	sll1.tripletOfSumK(sll2, sll3, k);
}
main();

Output

 Given Lists
 5 → 2 → -2 → 1 → 3 → 6 → NULL
 -1 → 2 → 5 → 4 → 9 → -9 → NULL
 1 → 2 → 8 → 4 → 3 → 6 → NULL
 Sum : 22
 Triplet : (5,9,8)
#    Python 3 program for
#    Find a triplet from three linked lists with given sum

#  Linked list node
class LinkNode :
	def __init__(self, data) :
		self.data = data
		self.next = None
	

class SingleLL :
	def __init__(self) :
		self.head = None
		self.tail = None
	
	#  Add new Node at end of linked list 
	def addNode(self, data) :
		node = LinkNode(data)
		if (self.head == None) :
			self.head = node
		else :
			#  Append the node at last position
			self.tail.next = node
		
		self.tail = node
	
	#  Display linked list element
	def display(self) :
		if (self.head == None) :
			return
		
		temp = self.head
		#  iterating linked list elements
		while (temp != None) :
			print("", temp.data ,"→", end = "")
			#  Visit to next node
			temp = temp.next
		
		print(" NULL")
	
	def tripletOfSumK(self, l2, l3, k) :
		if (self.head == None or l2.head == None or l3.head == None) :
			#   [Case Empty List]
			print(" Given Sum triplet not exist")
			return
		
		print("\n Given Lists ")
		self.display()
		l2.display()
		l3.display()
		print(" Sum : ", k ," ")
		t1 = self.head
		t2 = l2.head
		t3 = l3.head
		#  Compare linked list node
		while (t1 != None) :
			while (t2 != None) :
				while (t3 != None) :
					if (t1.data + t2.data + t3.data == k) :
						print(" Triplet : (", t1.data ,",", 
                              t2.data ,",", 
                              t3.data ,")", 
                              end = "")
						return
					
					#  Visit to next node
					t3 = t3.next
				
				#  Visit to next node
				t2 = t2.next
				t3 = l3.head
			
			#  Visit to next node
			t1 = t1.next
			t2 = l2.head
		
		print(" Triplet of sum ", k ," not found ")
	

def main() :
	sll1 = SingleLL()
	sll2 = SingleLL()
	sll3 = SingleLL()
	#  First linked list
	#   5 → 2 → -2 → 1 → 3 → 6 → NULL
	sll1.addNode(5)
	sll1.addNode(2)
	sll1.addNode(-2)
	sll1.addNode(1)
	sll1.addNode(3)
	sll1.addNode(6)
	#  Second linked list
	#   -1 → 2 → 5 → 4 → 9 → -9 → NULL
	sll2.addNode(-1)
	sll2.addNode(2)
	sll2.addNode(5)
	sll2.addNode(4)
	sll2.addNode(9)
	sll2.addNode(-9)
	#  Third linked list
	#   1 → 2 → 8 → 4 → 3 → 6 → NULL
	sll3.addNode(1)
	sll3.addNode(2)
	sll3.addNode(8)
	sll3.addNode(4)
	sll3.addNode(3)
	sll3.addNode(6)
	k = 22
	#  Test 
	sll1.tripletOfSumK(sll2, sll3, k)

if __name__ == "__main__": main()

Output

 Given Lists
 5 → 2 → -2 → 1 → 3 → 6 → NULL
 -1 → 2 → 5 → 4 → 9 → -9 → NULL
 1 → 2 → 8 → 4 → 3 → 6 → NULL
 Sum :  22
 Triplet : ( 5 , 9 , 8 )
#    Ruby program for
#    Find a triplet from three linked lists with given sum

#  Linked list node
class LinkNode 
	# Define the accessor and reader of class LinkNode
	attr_reader :data, :next
	attr_accessor :data, :next
	def initialize(data) 
		self.data = data
		self.next = nil
	end

end

class SingleLL 
	# Define the accessor and reader of class SingleLL
	attr_reader :head, :tail
	attr_accessor :head, :tail
	def initialize() 
		self.head = nil
		self.tail = nil
	end

	#  Add new Node at end of linked list 
	def addNode(data) 
		node = LinkNode.new(data)
		if (self.head == nil) 
			self.head = node
		else
 
			#  Append the node at last position
			self.tail.next = node
		end

		self.tail = node
	end

	#  Display linked list element
	def display() 
		if (self.head == nil) 
			return
		end

		temp = self.head
		#  iterating linked list elements
		while (temp != nil) 
			print(" ", temp.data ," →")
			#  Visit to next node
			temp = temp.next
		end

		print(" NULL\n")
	end

	def tripletOfSumK(l2, l3, k) 
		if (self.head == nil || l2.head == nil || l3.head == nil) 
			#   [Case Empty List]
			print(" Given Sum triplet not exist\n")
			return
		end

		print("\n Given Lists \n")
		self.display()
		l2.display()
		l3.display()
		print(" Sum : ", k ," \n")
		t1 = self.head
		t2 = l2.head
		t3 = l3.head
		#  Compare linked list node
		while (t1 != nil) 
			while (t2 != nil) 
				while (t3 != nil) 
					if (t1.data + t2.data + t3.data == k) 
						print(" Triplet : (", 
                              t1.data ,",", 
                              t2.data ,",", 
                              t3.data ,")")
						return
					end

					#  Visit to next node
					t3 = t3.next
				end

				#  Visit to next node
				t2 = t2.next
				t3 = l3.head
			end

			#  Visit to next node
			t1 = t1.next
			t2 = l2.head
		end

		print(" Triplet of sum ", k ," not found \n")
	end

end

def main() 
	sll1 = SingleLL.new()
	sll2 = SingleLL.new()
	sll3 = SingleLL.new()
	#  First linked list
	#   5 → 2 → -2 → 1 → 3 → 6 → NULL
	sll1.addNode(5)
	sll1.addNode(2)
	sll1.addNode(-2)
	sll1.addNode(1)
	sll1.addNode(3)
	sll1.addNode(6)
	#  Second linked list
	#   -1 → 2 → 5 → 4 → 9 → -9 → NULL
	sll2.addNode(-1)
	sll2.addNode(2)
	sll2.addNode(5)
	sll2.addNode(4)
	sll2.addNode(9)
	sll2.addNode(-9)
	#  Third linked list
	#   1 → 2 → 8 → 4 → 3 → 6 → NULL
	sll3.addNode(1)
	sll3.addNode(2)
	sll3.addNode(8)
	sll3.addNode(4)
	sll3.addNode(3)
	sll3.addNode(6)
	k = 22
	#  Test 
	sll1.tripletOfSumK(sll2, sll3, k)
end

main()

Output

 Given Lists 
 5 → 2 → -2 → 1 → 3 → 6 → NULL
 -1 → 2 → 5 → 4 → 9 → -9 → NULL
 1 → 2 → 8 → 4 → 3 → 6 → NULL
 Sum : 22 
 Triplet : (5,9,8)
/*
    Scala program for
    Find a triplet from three linked lists with given sum
*/
// Linked list node
class LinkNode(var data: Int,
	var next: LinkNode)
{
	def this(data: Int)
	{
		this(data,null);
	}
}
class SingleLL(var head: LinkNode,
	var tail: LinkNode)
{
	def this()
	{
		this(null,null);
	}
	// Add new Node at end of linked list 
	def addNode(data: Int): Unit = {
		var node: LinkNode = new LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail.next = node;
		}
		this.tail = node;
	}
	// Display linked list element
	def display(): Unit = {
		if (this.head == null)
		{
			return;
		}
		var temp: LinkNode = this.head;
		// iterating linked list elements
		while (temp != null)
		{
			print(" " + temp.data + " →");
			// Visit to next node
			temp = temp.next;
		}
		print(" NULL\n");
	}
	def tripletOfSumK(l2: SingleLL, l3: SingleLL, k: Int): Unit = {
		if (this.head == null || l2.head == null || l3.head == null)
		{
			//  [Case Empty List]
			print(" Given Sum triplet not exist\n");
			return;
		}
		print("\n Given Lists \n");
		this.display();
		l2.display();
		l3.display();
		print(" Sum : " + k + " \n");
		var t1: LinkNode = this.head;
		var t2: LinkNode = l2.head;
		var t3: LinkNode = l3.head;
		// Compare linked list node
		while (t1 != null)
		{
			while (t2 != null)
			{
				while (t3 != null)
				{
					if (t1.data + t2.data + t3.data == k)
					{
						print(" Triplet : (" + 
                              t1.data + "," + 
                              t2.data + "," + 
                              t3.data + ")");
						return;
					}
					// Visit to next node
					t3 = t3.next;
				}
				// Visit to next node
				t2 = t2.next;
				t3 = l3.head;
			}
			// Visit to next node
			t1 = t1.next;
			t2 = l2.head;
		}
		print(" Triplet of sum " + k + " not found \n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var sll1: SingleLL = new SingleLL();
		var sll2: SingleLL = new SingleLL();
		var sll3: SingleLL = new SingleLL();
		// First linked list
		//  5 → 2 → -2 → 1 → 3 → 6 → NULL
		sll1.addNode(5);
		sll1.addNode(2);
		sll1.addNode(-2);
		sll1.addNode(1);
		sll1.addNode(3);
		sll1.addNode(6);
		// Second linked list
		//  -1 → 2 → 5 → 4 → 9 → -9 → NULL
		sll2.addNode(-1);
		sll2.addNode(2);
		sll2.addNode(5);
		sll2.addNode(4);
		sll2.addNode(9);
		sll2.addNode(-9);
		// Third linked list
		//  1 → 2 → 8 → 4 → 3 → 6 → NULL
		sll3.addNode(1);
		sll3.addNode(2);
		sll3.addNode(8);
		sll3.addNode(4);
		sll3.addNode(3);
		sll3.addNode(6);
		var k: Int = 22;
		// Test 
		sll1.tripletOfSumK(sll2, sll3, k);
	}
}

Output

 Given Lists
 5 → 2 → -2 → 1 → 3 → 6 → NULL
 -1 → 2 → 5 → 4 → 9 → -9 → NULL
 1 → 2 → 8 → 4 → 3 → 6 → NULL
 Sum : 22
 Triplet : (5,9,8)
/*
    Swift 4 program for
    Find a triplet from three linked lists with given sum
*/
// Linked list node
class LinkNode
{
	var data: Int;
	var next: LinkNode? ;
	init(_ data: Int)
	{
		self.data = data;
		self.next = nil;
	}
}
class SingleLL
{
	var head: LinkNode? ;
	var tail: LinkNode? ;
	init()
	{
		self.head = nil;
		self.tail = nil;
	}
	// Add new Node at end of linked list 
	func addNode(_ data: Int)
	{
		let node: LinkNode = LinkNode(data);
		if (self.head == nil)
		{
			self.head = node;
		}
		else
		{
			// Append the node at last position
			self.tail!.next = node;
		}
		self.tail = node;
	}
	// Display linked list element
	func display()
	{
		if (self.head == nil)
		{
			return;
		}
		var temp: LinkNode? = self.head;
		// iterating linked list elements
		while (temp  != nil)
		{
			print("", temp!.data ,"→", terminator: "");
			// Visit to next node
			temp = temp!.next;
		}
		print(" NULL");
	}
	func tripletOfSumK(_ l2: SingleLL? , _ l3 : SingleLL? , _ k : Int)
	{
		if (self.head == nil || l2!.head == nil || l3!.head == nil)
		{
			//  [Case Empty List]
			print(" Given Sum triplet not exist");
			return;
		}
		print("\n Given Lists ");
		self.display();
		l2!.display();
		l3!.display();
		print(" Sum : ", k ," ");
		var t1: LinkNode? = self.head;
		var t2: LinkNode? = l2!.head;
		var t3: LinkNode? = l3!.head;
		// Compare linked list node
		while (t1  != nil)
		{
			while (t2  != nil)
			{
				while (t3  != nil)
				{
					if (t1!.data + t2!.data + t3!.data == k)
					{
						print(" Triplet : (", 
                              t1!.data ,",", 
                              t2!.data ,",", 
                              t3!.data ,")", terminator: "");
						return;
					}
					// Visit to next node
					t3 = t3!.next;
				}
				// Visit to next node
				t2 = t2!.next;
				t3 = l3!.head;
			}
			// Visit to next node
			t1 = t1!.next;
			t2 = l2!.head;
		}
		print(" Triplet of sum ", k ," not found ");
	}
}
func main()
{
	let sll1: SingleLL = SingleLL();
	let sll2: SingleLL = SingleLL();
	let sll3: SingleLL = SingleLL();
	// First linked list
	//  5 → 2 → -2 → 1 → 3 → 6 → NULL
	sll1.addNode(5);
	sll1.addNode(2);
	sll1.addNode(-2);
	sll1.addNode(1);
	sll1.addNode(3);
	sll1.addNode(6);
	// Second linked list
	//  -1 → 2 → 5 → 4 → 9 → -9 → NULL
	sll2.addNode(-1);
	sll2.addNode(2);
	sll2.addNode(5);
	sll2.addNode(4);
	sll2.addNode(9);
	sll2.addNode(-9);
	// Third linked list
	//  1 → 2 → 8 → 4 → 3 → 6 → NULL
	sll3.addNode(1);
	sll3.addNode(2);
	sll3.addNode(8);
	sll3.addNode(4);
	sll3.addNode(3);
	sll3.addNode(6);
	let k: Int = 22;
	// Test 
	sll1.tripletOfSumK(sll2, sll3, k);
}
main();

Output

 Given Lists
 5 → 2 → -2 → 1 → 3 → 6 → NULL
 -1 → 2 → 5 → 4 → 9 → -9 → NULL
 1 → 2 → 8 → 4 → 3 → 6 → NULL
 Sum :  22
 Triplet : ( 5 , 9 , 8 )
/*
    Kotlin program for
    Find a triplet from three linked lists with given sum
*/
// Linked list node
class LinkNode
{
	var data: Int;
	var next: LinkNode ? ;
	constructor(data: Int)
	{
		this.data = data;
		this.next = null;
	}
}
class SingleLL
{
	var head: LinkNode ? ;
	var tail: LinkNode ? ;
	constructor()
	{
		this.head = null;
		this.tail = null;
	}
	// Add new Node at end of linked list 
	fun addNode(data: Int): Unit
	{
		val node: LinkNode = LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail?.next = node;
		}
		this.tail = node;
	}
	// Display linked list element
	fun display(): Unit
	{
		if (this.head == null)
		{
			return;
		}
		var temp: LinkNode ? = this.head;
		// iterating linked list elements
		while (temp != null)
		{
			print(" " + temp.data + " →");
			// Visit to next node
			temp = temp.next;
		}
		print(" NULL\n");
	}
	fun tripletOfSumK(l2: SingleLL, l3 : SingleLL, k : Int): Unit
	{
		if (this.head == null || l2.head == null || l3.head == null)
		{
			//  [Case Empty List]
			print(" Given Sum triplet not exist\n");
			return;
		}
		print("\n Given Lists \n");
		this.display();
		l2.display();
		l3.display();
		print(" Sum : " + k + " \n");
		var t1: LinkNode ? = this.head;
		var t2: LinkNode ? = l2.head;
		var t3: LinkNode ? = l3.head;
		// Compare linked list node
		while (t1 != null)
		{
			while (t2 != null)
			{
				while (t3 != null)
				{
					if (t1.data + t2.data + t3.data == k)
					{
						print(" Triplet : (" + 
                              t1.data + "," + t2.data + "," + 
                              t3.data + ")");
						return;
					}
					// Visit to next node
					t3 = t3.next;
				}
				// Visit to next node
				t2 = t2.next;
				t3 = l3.head;
			}
			// Visit to next node
			t1 = t1.next;
			t2 = l2.head;
		}
		print(" Triplet of sum " + k + " not found \n");
	}
}
fun main(args: Array < String > ): Unit
{
	val sll1: SingleLL = SingleLL();
	val sll2: SingleLL = SingleLL();
	val sll3: SingleLL = SingleLL();
	// First linked list
	//  5 → 2 → -2 → 1 → 3 → 6 → NULL
	sll1.addNode(5);
	sll1.addNode(2);
	sll1.addNode(-2);
	sll1.addNode(1);
	sll1.addNode(3);
	sll1.addNode(6);
	// Second linked list
	//  -1 → 2 → 5 → 4 → 9 → -9 → NULL
	sll2.addNode(-1);
	sll2.addNode(2);
	sll2.addNode(5);
	sll2.addNode(4);
	sll2.addNode(9);
	sll2.addNode(-9);
	// Third linked list
	//  1 → 2 → 8 → 4 → 3 → 6 → NULL
	sll3.addNode(1);
	sll3.addNode(2);
	sll3.addNode(8);
	sll3.addNode(4);
	sll3.addNode(3);
	sll3.addNode(6);
	val k: Int = 22;
	// Test 
	sll1.tripletOfSumK(sll2, sll3, k);
}

Output

 Given Lists
 5 → 2 → -2 → 1 → 3 → 6 → NULL
 -1 → 2 → 5 → 4 → 9 → -9 → NULL
 1 → 2 → 8 → 4 → 3 → 6 → NULL
 Sum : 22
 Triplet : (5,9,8)
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment