Dadas tres listas enlazadas, digamos a, b y c, encuentre un Node de cada lista tal que la suma de los valores de los Nodes sea igual a un número dado.
Por ejemplo, si las tres listas enlazadas son 12->6->29, 23->5->8 y 90->20->59, y el número dado es 101, la salida debería ser triple “6 5 90 ”.
En las siguientes soluciones, se supone que el tamaño de las tres listas enlazadas es el mismo para simplificar el análisis. Las siguientes soluciones también funcionan para listas enlazadas de diferentes tamaños.
Un método simple para resolver este problema es ejecutar tres bucles anidados. El ciclo más externo toma un elemento de la lista a, el ciclo del medio toma un elemento de b y el ciclo más interno toma de c. El ciclo más interno también verifica si la suma de los valores de los Nodes actuales de a, b y c es igual al número dado. La complejidad temporal de este método será O(n^3).
La clasificación se puede utilizar para reducir la complejidad del tiempo a O(n*n). Los siguientes son los pasos detallados.
1) Ordenar la lista b en orden ascendente y la lista c en orden descendente.
2) Después de ordenar b y c, elija uno por uno un elemento de la lista a y encuentre el par recorriendo b y c. Consulte isSumSorted() en el siguiente código. La idea es similar al algoritmo cuadrático del problema de 3 sumas .
El siguiente código implementa solo el paso 2. La solución se puede modificar fácilmente para listas no ordenadas agregando el código de clasificación combinado que se analiza aquí .
C++
// C++ program to find a triplet
// from three linked lists with
// sum equal to a given number
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
class Node
{
public:
int data;
Node* next;
};
/* A utility function to insert
a node at the beginning of a
linked list*/
void push (Node** head_ref, int new_data)
{
/* allocate node */
Node* new_node = new Node();
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* A function to check if there are three elements in a, b
and c whose sum is equal to givenNumber. The function
assumes that the list b is sorted in ascending order
and c is sorted in descending order. */
bool isSumSorted(Node *headA, Node *headB,
Node *headC, int givenNumber)
{
Node *a = headA;
// Traverse through all nodes of a
while (a != NULL)
{
Node *b = headB;
Node *c = headC;
// For every node of list a, prick two nodes
// from lists b abd c
while (b != NULL && c != NULL)
{
// If this a triplet with given sum, print
// it and return true
int sum = a->data + b->data + c->data;
if (sum == givenNumber)
{
cout << "Triplet Found: " << a->data << " " <<
b->data << " " << c->data;
return true;
}
// If sum of this triplet is smaller, look for
// greater values in b
else if (sum < givenNumber)
b = b->next;
else // If sum is greater, look for smaller values in c
c = c->next;
}
a = a->next; // Move ahead in list a
}
cout << "No such triplet";
return false;
}
/* Driver code*/
int main()
{
/* Start with the empty list */
Node* headA = NULL;
Node* headB = NULL;
Node* headC = NULL;
/*create a linked list 'a' 10->15->5->20 */
push (&headA, 20);
push (&headA, 4);
push (&headA, 15);
push (&headA, 10);
/*create a sorted linked list 'b' 2->4->9->10 */
push (&headB, 10);
push (&headB, 9);
push (&headB, 4);
push (&headB, 2);
/*create another sorted
linked list 'c' 8->4->2->1 */
push (&headC, 1);
push (&headC, 2);
push (&headC, 4);
push (&headC, 8);
int givenNumber = 25;
isSumSorted (headA, headB, headC, givenNumber);
return 0;
}
// This code is contributed by rathbhupendra
C
// C program to find a triplet from three linked lists with
// sum equal to a given number
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
/* Link list node */
struct Node
{
int data;
struct Node* next;
};
/* A utility function to insert a node at the beginning of a
linked list*/
void push (struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* A function to check if there are three elements in a, b
and c whose sum is equal to givenNumber. The function
assumes that the list b is sorted in ascending order
and c is sorted in descending order. */
bool isSumSorted(struct Node *headA, struct Node *headB,
struct Node *headC, int givenNumber)
{
struct Node *a = headA;
// Traverse through all nodes of a
while (a != NULL)
{
struct Node *b = headB;
struct Node *c = headC;
// For every node of list a, prick two nodes
// from lists b abd c
while (b != NULL && c != NULL)
{
// If this a triplet with given sum, print
// it and return true
int sum = a->data + b->data + c->data;
if (sum == givenNumber)
{
printf ("Triplet Found: %d %d %d ", a->data,
b->data, c->data);
return true;
}
// If sum of this triplet is smaller, look for
// greater values in b
else if (sum < givenNumber)
b = b->next;
else // If sum is greater, look for smaller values in c
c = c->next;
}
a = a->next; // Move ahead in list a
}
printf ("No such triplet");
return false;
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* headA = NULL;
struct Node* headB = NULL;
struct Node* headC = NULL;
/*create a linked list 'a' 10->15->5->20 */
push (&headA, 20);
push (&headA, 4);
push (&headA, 15);
push (&headA, 10);
/*create a sorted linked list 'b' 2->4->9->10 */
push (&headB, 10);
push (&headB, 9);
push (&headB, 4);
push (&headB, 2);
/*create another sorted linked list 'c' 8->4->2->1 */
push (&headC, 1);
push (&headC, 2);
push (&headC, 4);
push (&headC, 8);
int givenNumber = 25;
isSumSorted (headA, headB, headC, givenNumber);
return 0;
}
Java
// Java program to find a triplet from three linked lists with
// sum equal to a given number
class LinkedList
{
Node head; // head of list
/* Linked list Node*/
class Node
{
int data;
Node next;
Node(int d) {data = d; next = null; }
}
/* A function to check if there are three elements in a, b
and c whose sum is equal to givenNumber. The function
assumes that the list b is sorted in ascending order and
c is sorted in descending order. */
boolean isSumSorted(LinkedList la, LinkedList lb, LinkedList lc,
int givenNumber)
{
Node a = la.head;
// Traverse all nodes of la
while (a != null)
{
Node b = lb.head;
Node c = lc.head;
// for every node in la pick 2 nodes from lb and lc
while (b != null && c!=null)
{
int sum = a.data + b.data + c.data;
if (sum == givenNumber)
{
System.out.println("Triplet found " + a.data +
" " + b.data + " " + c.data);
return true;
}
// If sum is smaller then look for greater value of b
else if (sum < givenNumber)
b = b.next;
else
c = c.next;
}
a = a.next;
}
System.out.println("No Triplet found");
return false;
}
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Driver program to test above functions */
public static void main(String args[])
{
LinkedList llist1 = new LinkedList();
LinkedList llist2 = new LinkedList();
LinkedList llist3 = new LinkedList();
/* Create Linked List llist1 100->15->5->20 */
llist1.push(20);
llist1.push(5);
llist1.push(15);
llist1.push(100);
/*create a sorted linked list 'b' 2->4->9->10 */
llist2.push(10);
llist2.push(9);
llist2.push(4);
llist2.push(2);
/*create another sorted linked list 'c' 8->4->2->1 */
llist3.push(1);
llist3.push(2);
llist3.push(4);
llist3.push(8);
int givenNumber = 25;
llist1.isSumSorted(llist1,llist2,llist3,givenNumber);
}
} /* This code is contributed by Rajat Mishra */
Python
# Python program to find a triplet
# from three linked lists with
# sum equal to a given number
# Link list node
class Node:
def __init__(self, new_data):
self.data = new_data
self.next = None
# A utility function to insert
# a node at the beginning of a
# linked list
def push ( head_ref, new_data) :
# allocate node
new_node = Node(0)
# put in the data
new_node.data = new_data
# link the old list off the new node
new_node.next = (head_ref)
# move the head to point to the new node
(head_ref) = new_node
return head_ref;
# A function to check if there are three elements in a, b
# and c whose sum is equal to givenNumber. The function
# assumes that the list b is sorted in ascending order
# and c is sorted in descending order.
def isSumSorted(headA, headB,headC, givenNumber) :
a = headA
# Traverse through all nodes of a
while (a != None) :
b = headB
c = headC
# For every node of list a, prick two nodes
# from lists b abd c
while (b != None and c != None) :
# If this a triplet with given sum, print
# it and return true
sum = a.data + b.data + c.data
if (sum == givenNumber) :
print "Triplet Found: " , a.data , " " , b.data , " " , c.data,
return True
# If sum of this triplet is smaller, look for
# greater values in b
elif (sum < givenNumber):
b = b.next
else :# If sum is greater, look for smaller values in c
c = c.next
a = a.next # Move ahead in list a
print("No such triplet")
return False
# Driver code
# Start with the empty list
headA = None
headB = None
headC = None
# create a linked list 'a' 10.15.5.20
headA = push (headA, 20)
headA = push (headA, 4)
headA = push (headA, 15)
headA = push (headA, 10)
# create a sorted linked list 'b' 2.4.9.10
headB = push (headB, 10)
headB = push (headB, 9)
headB = push (headB, 4)
headB = push (headB, 2)
# create another sorted
# linked list 'c' 8.4.2.1
headC = push (headC, 1)
headC = push (headC, 2)
headC = push (headC, 4)
headC = push (headC, 8)
givenNumber = 25
isSumSorted (headA, headB, headC, givenNumber)
# This code is contributed by Arnab Kundu
C#
// C# program to find a triplet
// from three linked lists with
// sum equal to a given number
using System;
public class LinkedList
{
public Node head; // head of list
/* Linked list Node*/
public class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d; next = null;
}
}
/* A function to check if there
are three elements in a, b
and c whose sum is equal to
givenNumber. The function
assumes that the list b is
sorted in ascending order and
c is sorted in descending order. */
bool isSumSorted(LinkedList la, LinkedList lb,
LinkedList lc, int givenNumber)
{
Node a = la.head;
// Traverse all nodes of la
while (a != null)
{
Node b = lb.head;
Node c = lc.head;
// for every node in la pick
// 2 nodes from lb and lc
while (b != null && c!=null)
{
int sum = a.data + b.data + c.data;
if (sum == givenNumber)
{
Console.WriteLine("Triplet found " + a.data +
" " + b.data + " " + c.data);
return true;
}
// If sum is smaller then
// look for greater value of b
else if (sum < givenNumber)
b = b.next;
else
c = c.next;
}
a = a.next;
}
Console.WriteLine("No Triplet found");
return false;
}
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Driver code*/
public static void Main(String []args)
{
LinkedList llist1 = new LinkedList();
LinkedList llist2 = new LinkedList();
LinkedList llist3 = new LinkedList();
/* Create Linked List llist1 100->15->5->20 */
llist1.push(20);
llist1.push(5);
llist1.push(15);
llist1.push(100);
/*create a sorted linked list 'b' 2->4->9->10 */
llist2.push(10);
llist2.push(9);
llist2.push(4);
llist2.push(2);
/*create another sorted linked list 'c' 8->4->2->1 */
llist3.push(1);
llist3.push(2);
llist3.push(4);
llist3.push(8);
int givenNumber = 25;
llist1.isSumSorted(llist1,llist2,llist3,givenNumber);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find a triplet from three linked lists with
// sum equal to a given number
/* Linked list Node*/
class Node
{
constructor(d)
{
this.data = d;
this.next = null;
}
}
/* A function to check if there are three elements in a, b
and c whose sum is equal to givenNumber. The function
assumes that the list b is sorted in ascending order and
c is sorted in descending order. */
function isSumSorted(la,lb,lc,givenNumber)
{
let a = la;
// Traverse all nodes of la
while (a != null)
{
let b = lb;
let c = lc;
// for every node in la pick 2 nodes from lb and lc
while (b != null && c!=null)
{
let sum = a.data + b.data + c.data;
if (sum == givenNumber)
{
document.write("Triplet found " + a.data +
" " + b.data + " " + c.data+"<br>");
return true;
}
// If sum is smaller then look for greater value of b
else if (sum < givenNumber)
b = b.next;
else
c = c.next;
}
a = a.next;
}
document.write("No Triplet found<br>");
return false;
}
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
function push(head_ref,new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
let new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref;
}
let headA =null;
headA = push (headA, 20)
headA = push (headA, 4)
headA = push (headA, 15)
headA = push (headA, 10)
// create a sorted linked list 'b' 2.4.9.10
let headB = null;
headB = push (headB, 10)
headB = push (headB, 9)
headB = push (headB, 4)
headB = push (headB, 2)
// create another sorted
// linked list 'c' 8.4.2.1
let headC = null;
headC = push (headC, 1)
headC = push (headC, 2)
headC = push (headC, 4)
headC = push (headC, 8)
let givenNumber = 25
isSumSorted (headA, headB, headC, givenNumber)
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Triplet Found: 15 2 8
Complejidad temporal: O(n 2 )
Las listas enlazadas b y c se pueden ordenar en tiempo O (nLogn) usando Merge Sort (Ver esto ). El paso 2 toma el tiempo O(n*n). Entonces, la complejidad temporal general es O(nlogn) + O(nlogn) + O(n*n) = O(n*n).
En este enfoque, las listas enlazadas b y c se ordenan primero, por lo que se perderá su orden original. Si queremos conservar el orden original de b y c, podemos crear una copia de b y c.
Espacio Auxiliar: O(1)
Aquí se usa espacio adicional constante, pero si deseamos mantener el orden original de las listas b y c, nuestra complejidad de tiempo se convertirá en O(n) ya que se usará espacio adicional para almacenar los elementos ordenados de la lista.
Este artículo fue compilado por Abhinav Priyadarshi y revisado por el equipo de GeeksforGeeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA