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