Dadas tres listas enlazadas, encuentre todos los elementos comunes entre las tres listas enlazadas.
Ejemplos:
Input : 10 15 20 25 12 10 12 13 15 10 12 15 24 25 26 Output : 10 12 15 Input : 1 2 3 4 5 1 2 3 4 6 9 8 1 2 4 5 10 Output : 1 2 4
Método 1: (Simple)
Use tres punteros para iterar las tres listas vinculadas dadas y, si hay algún elemento común, imprima ese elemento.
La complejidad temporal de la solución anterior será O(N*N*N)
Método 2: (Usar Merge Sort)
En este método, primero ordenamos las tres listas y luego recorremos las listas ordenadas para obtener la intersección.
Los siguientes son los pasos a seguir para obtener la intersección de tres listas:
1) Ordenar la primera Lista Vinculada utilizando la ordenación por fusión. Este paso toma tiempo O(mLogm). Consulte esta publicación para obtener detalles de este paso.
2) Ordene la segunda lista enlazada utilizando la ordenación por fusión. Este paso toma tiempo O(nLogn). Consulte esta publicación para obtener detalles de este paso.
3) Ordene la tercera lista enlazada utilizando la ordenación por fusión. Este paso toma tiempo O(pLogp). Consulte esta publicación para obtener detalles de este paso.
3) Escanea linealmente tres listas ordenadas para obtener la intersección. Este paso toma O(m + n + p) tiempo. Este paso se puede implementar usando el mismo algoritmo que el algoritmo de arreglos ordenados discutido aquí .
La complejidad temporal de este método es O(mLogm + nLogn + plogp), que es mejor que la complejidad temporal del método 1.
Método 3: (Hashing)
Los siguientes son los pasos a seguir para obtener la intersección de tres listas usando hash:
1) Cree una tabla hash vacía. Repita la primera lista enlazada y marque la frecuencia de todos los elementos como 1 en la tabla hash. Este paso lleva O(m) tiempo.
2) Iterar a través de la segunda lista enlazada y si la frecuencia del elemento actual es 1 en la tabla hash, márquelo como 2. Este paso toma O (n) tiempo.
3) Iterar la tercera lista enlazada y si la frecuencia del elemento actual es 2 en la tabla hash márquelo como 3. Este paso toma tiempo O(p).
4) Ahora vuelva a iterar la primera lista enlazada para verificar la frecuencia de los elementos. si existe un elemento con frecuencia tres en la tabla hash, estará presente en la intersección de tres listas enlazadas. Este paso lleva O(m) tiempo.
La complejidad temporal de este método es O(m + n + p), que es mejor que la complejidad temporal de los métodos 1 y 2.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find common element
// in three unsorted linked list
#include <bits/stdc++.h>
#define max 1000000
using namespace std;
/* 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)
{
struct Node* new_node =
(struct Node *)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* print the common element in between
given three linked list*/
void Common(struct Node* head1,
struct Node* head2, struct Node* head3)
{
// Creating empty hash table;
unordered_map<int, int> hash;
struct Node* p = head1;
while (p != NULL) {
// set frequency by 1
hash[p->data] = 1;
p = p->next;
}
struct Node* q = head2;
while (q != NULL) {
// if the element is already exist in the
// linked list set its frequency 2
if (hash.find(q->data) != hash.end())
hash[q->data] = 2;
q = q->next;
}
struct Node* r = head3;
while (r != NULL) {
if (hash.find(r->data) != hash.end() &&
hash[r->data] == 2)
// if the element frequency is 2 it means
// its present in both the first and second
// linked list set its frequency 3
hash[r->data] = 3;
r = r->next;
}
for (auto x : hash) {
// if current frequency is 3 its means
// element is common in all the given
// linked list
if (x.second == 3)
cout << x.first << " ";
}
}
// Driver code
int main()
{
// first list
struct Node* head1 = NULL;
push(&head1, 20);
push(&head1, 5);
push(&head1, 15);
push(&head1, 10);
// second list
struct Node* head2 = NULL;
push(&head2, 10);
push(&head2, 20);
push(&head2, 15);
push(&head2, 8);
// third list
struct Node* head3 = NULL;
push(&head3, 10);
push(&head3, 2);
push(&head3, 15);
push(&head3, 20);
Common(head1, head2, head3);
return 0;
}
Java
// Java program to find common element
// in three unsorted linked list
import java.util.*;
class GFG
{
static int max = 1000000;
/* Link list node */
static class Node
{
int data;
Node next;
};
/* A utility function to insert a node
at the beginning of a linked list */
static Node push(Node head_ref,
int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
return head_ref;
}
/* print the common element in between
given three linked list*/
static void Common(Node head1,
Node head2,
Node head3)
{
// Creating empty hash table;
HashMap<Integer,
Integer> hash = new HashMap<Integer,
Integer>();
Node p = head1;
while (p != null)
{
// set frequency by 1
hash. put(p.data, 1);
p = p.next;
}
Node q = head2;
while (q != null)
{
// if the element is already exist in the
// linked list set its frequency 2
if (hash.containsKey(q.data))
hash. put(q.data, 2);
q = q.next;
}
Node r = head3;
while (r != null)
{
if (hash.containsKey(r.data)&&
hash.get(r.data) == 2)
// if the element frequency is 2 it means
// its present in both the first and second
// linked list set its frequency 3
hash. put(r.data, 3);
r = r.next;
}
for (Map.Entry<Integer,
Integer> x : hash.entrySet())
{
// if current frequency is 3 its means
// element is common in all the given
// linked list
if (x.getValue() == 3)
System.out.println(x.getKey() + " ");
}
}
// Driver code
public static void main(String[] args)
{
// first list
Node head1 = null;
head1 = push(head1, 20);
head1 = push(head1, 5);
head1 = push(head1, 15);
head1 = push(head1, 10);
// second list
Node head2 = null;
head2 = push(head2, 10);
head2 = push(head2, 20);
head2 = push(head2, 15);
head2 = push(head2, 8);
// third list
Node head3 = null;
head3 = push(head3, 10);
head3 = push(head3, 2);
head3 = push(head3, 15);
head3 = push(head3, 20);
Common(head1, head2, head3);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find common element # in three unsorted linked list max = 1000000 # Link list node class Node: def __init__(self, data): self.data = data self.next = None # A utility function to insert a node at the # beginning of a linked list def push( head_ref, new_data): new_node = Node(new_data) new_node.next = head_ref head_ref = new_node return head_ref # Print the common element in between # given three linked list def Common(head1, head2, head3): # Creating empty hash table; hash = dict() p = head1 while (p != None): # Set frequency by 1 hash[p.data] = 1 p = p.next q = head2 while (q != None): # If the element is already exist in the # linked list set its frequency 2 if (q.data in hash): hash[q.data] = 2 q = q.next r = head3 while (r != None): if (r.data in hash) and hash[r.data] == 2: # If the element frequency is 2 it means # its present in both the first and second # linked list set its frequency 3 hash[r.data] = 3 r = r.next for x in hash.keys(): # If current frequency is 3 its means # element is common in all the given # linked list if (hash[x] == 3): print(x, end = ' ') # Driver code if __name__=='__main__': # First list head1 = None head1 = push(head1, 20) head1 = push(head1, 5) head1 = push(head1, 15) head1 = push(head1, 10) # Second list head2 = None head2 = push(head2, 10) head2 = push(head2, 20) head2 = push(head2, 15) head2 = push(head2, 8) # Third list head3 = None head3 = push(head3, 10) head3 = push(head3, 2) head3 = push(head3, 15) head3 = push(head3, 20) Common(head1, head2, head3) # This code is contributed by rutvik_56
C#
// C# program to find common element
// in three unsorted linked list
using System;
using System.Collections.Generic;
class GFG
{
static int max = 1000000;
/* Link list node */
public class Node
{
public int data;
public Node next;
};
/* A utility function to insert a node
at the beginning of a linked list */
static Node push(Node head_ref,
int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
return head_ref;
}
/* print the common element in between
given three linked list*/
static void Common(Node head1,
Node head2,
Node head3)
{
// Creating empty hash table;
Dictionary<int,
int> hash = new Dictionary<int,
int>();
Node p = head1;
while (p != null)
{
// set frequency by 1
hash.Add(p.data, 1);
p = p.next;
}
Node q = head2;
while (q != null)
{
// if the element is already exist in the
// linked list set its frequency 2
if (hash.ContainsKey(q.data))
hash[q.data] = 2;
q = q.next;
}
Node r = head3;
while (r != null)
{
if (hash.ContainsKey(r.data)&&
hash[r.data] == 2)
// if the element frequency is 2 it means
// its present in both the first and
// second linked list set its frequency 3
hash[r.data] = 3;
r = r.next;
}
foreach(KeyValuePair<int, int> x in hash)
{
// if current frequency is 3 its means
// element is common in all the given
// linked list
if (x.Value == 3)
Console.Write(x.Key + " ");
}
}
// Driver code
public static void Main(String[] args)
{
// first list
Node head1 = null;
head1 = push(head1, 20);
head1 = push(head1, 5);
head1 = push(head1, 15);
head1 = push(head1, 10);
// second list
Node head2 = null;
head2 = push(head2, 10);
head2 = push(head2, 20);
head2 = push(head2, 15);
head2 = push(head2, 8);
// third list
Node head3 = null;
head3 = push(head3, 10);
head3 = push(head3, 2);
head3 = push(head3, 15);
head3 = push(head3, 20);
Common(head1, head2, head3);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program to find common element
// in three unsorted linked list
var max = 1000000;
/* Link list node */
class Node
{
constructor()
{
this.data = 0;
this.next = null;
}
};
/* A utility function to insert a node
at the beginning of a linked list */
function push(head_ref, new_data)
{
var new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
return head_ref;
}
/* print the common element in between
given three linked list*/
function Common(head1, head2, head3)
{
// Creating empty hash table;
var hash = new Map();
var p = head1;
while (p != null)
{
// set frequency by 1
hash.set(p.data, 1);
p = p.next;
}
var q = head2;
while (q != null)
{
// if the element is already exist in the
// linked list set its frequency 2
if (hash.has(q.data))
hash.set(q.data, 2);
q = q.next;
}
var r = head3;
while (r != null)
{
if (hash.has(r.data)&&
hash.get(r.data) == 2)
// if the element frequency is 2 it means
// its present in both the first and
// second linked list set its frequency 3
hash.set(r.data, 3);
r = r.next;
}
hash.forEach((value, key) => {
// if current frequency is 3 its means
// element is common in all the given
// linked list
if (value == 3)
document.write(key + " ");
});
}
// Driver code
// first list
var head1 = null;
head1 = push(head1, 20);
head1 = push(head1, 5);
head1 = push(head1, 15);
head1 = push(head1, 10);
// second list
var head2 = null;
head2 = push(head2, 10);
head2 = push(head2, 20);
head2 = push(head2, 15);
head2 = push(head2, 8);
// third list
var head3 = null;
head3 = push(head3, 10);
head3 = push(head3, 2);
head3 = push(head3, 15);
head3 = push(head3, 20);
Common(head1, head2, head3);
</script>
10 15 20
Complejidad del tiempo: O(m + n + p)
Publicación traducida automáticamente
Artículo escrito por Vishal_Khoda y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA