Dadas dos listas enlazadas, cree listas de unión e intersección que contengan la unión y la intersección de los elementos presentes en las listas dadas. El orden de los elementos en las listas de salida no importa. Ejemplos:
Input: List1: 10 -> 15 -> 4 -> 20 List2: 8 -> 4 -> 2 -> 10 Output: Intersection List: 4 -> 10 Union List: 2 -> 8 -> 20 -> 4 -> 15 -> 10 Explanation: In this two lists 4 and 10 nodes are common. The union lists contains all the nodes of both the lists. Input: List1: 1 -> 2 -> 3 -> 4 List2: 3 -> 4 -> 8 -> 10 Output: Intersection List: 3 -> 4 Union List: 1 -> 2 -> 3 -> 4 -> 8 -> 10 Explanation: In this two lists 4 and 3 nodes are common. The union lists contains all the nodes of both the lists.
Ya hemos discutido el Método 1 y el Método 2 de esta pregunta. En esta publicación, su Método-3 (Uso de hashing) se analiza con una Complejidad de tiempo de O(m+n), es decir, mejor que los dos métodos discutidos anteriormente.
Implementation:
1- Start traversing both the lists.
a) Store the current element of both lists
with its occurrence in the map.
2- For Union: Store all the elements of the map
in the resultant list.
3- For Intersection: Store all the elements only
with an occurrence of 2 as 2 denotes that
they are present in both the lists.
A continuación se muestra la implementación en C++ de los pasos anteriores.
CPP
// C++ program to find union and intersection of
// two unsorted linked lists in O(m+n) time.
#include <bits/stdc++.h>
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)
{
/* 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;
}
/* Utility function to store the
elements of both list */
void storeEle(struct Node* head1, struct Node* head2,
unordered_map<int, int>& eleOcc)
{
struct Node* ptr1 = head1;
struct Node* ptr2 = head2;
// Traverse both lists
while (ptr1 != NULL || ptr2 != NULL) {
// store element in the map
if (ptr1 != NULL) {
eleOcc[ptr1->data]++;
ptr1 = ptr1->next;
}
// store element in the map
if (ptr2 != NULL) {
eleOcc[ptr2->data]++;
ptr2 = ptr2->next;
}
}
}
/* Function to get the union of two
linked lists head1 and head2 */
struct Node* getUnion(
unordered_map<int, int> eleOcc)
{
struct Node* result = NULL;
// Push all the elements into
// the resultant list
for (auto it = eleOcc.begin(); it != eleOcc.end(); it++)
push(&result, it->first);
return result;
}
/* Function to get the intersection of
two linked lists head1 and head2 */
struct Node* getIntersection(
unordered_map<int, int> eleOcc)
{
struct Node* result = NULL;
// Push a node with an element
// having occurrence of 2 as that
// means the current element is
// present in both the lists
for (auto it = eleOcc.begin();
it != eleOcc.end(); it++)
if (it->second == 2)
push(&result, it->first);
// return resultant list
return result;
}
/* A utility function to print a linked list*/
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
// Prints union and intersection of
// lists with head1 and head2.
void printUnionIntersection(Node* head1,
Node* head2)
{
// Store all the elements of
// both lists in the map
unordered_map<int, int> eleOcc;
storeEle(head1, head2, eleOcc);
Node* intersection_list = getIntersection(eleOcc);
Node* union_list = getUnion(eleOcc);
printf("\nIntersection list is \n");
printList(intersection_list);
printf("\nUnion list is \n");
printList(union_list);
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head1 = NULL;
struct Node* head2 = NULL;
/* create a linked list 11->10->15->4->20 */
push(&head1, 1);
push(&head1, 2);
push(&head1, 3);
push(&head1, 4);
push(&head1, 5);
/* create a linked list 8->4->2->10 */
push(&head2, 1);
push(&head2, 3);
push(&head2, 5);
push(&head2, 6);
printf("First list is \n");
printList(head1);
printf("\nSecond list is \n");
printList(head2);
printUnionIntersection(head1, head2);
return 0;
}
Java
//Java program to find union and intersection of
// two unsorted linked lists in O(m+n) time.
import java.io.*;
import java.util.*;
class GFG {
static void printList(Node node)
{
while (node != null) {
System.out.print(node.data+" ");
node = node.next;
}
}
//Utility function to store the
//elements of both list
static void storeEle(Node head1, Node head2,Map<Integer, Integer> eleOcc)
{
Node ptr1 = head1;
Node ptr2 = head2;
// Traverse both lists
while (ptr1 != null || ptr2 != null) {
// store element in the map
if (ptr1 != null) {
if(eleOcc.get(ptr1.data)==null){
eleOcc.put(ptr1.data,1);
}else{
eleOcc.put(ptr1.data,eleOcc.get(ptr1.data)+1);
}
ptr1 = ptr1.next;
}
// store element in the map
if (ptr2 != null) {
if(eleOcc.get(ptr2.data)==null){
eleOcc.put(ptr2.data,1);
}else{
eleOcc.put(ptr2.data,eleOcc.get(ptr2.data)+1);
}
ptr2 = ptr2.next;
}
}
}
//Function to get the union of two
//linked lists head1 and head2
static Node getUnion(Map<Integer, Integer> eleOcc)
{
Node result = null;
// Push all the elements into
// the resultant list
for (int key:eleOcc.keySet()){
Node node = new Node(key);
node.next=result;
result=node;
}
return result;
}
// Prints union and intersection of
// lists with head1 and head2.
static void printUnionIntersection(Node head1,Node head2)
{
// Store all the elements of
// both lists in the map
Map<Integer, Integer> eleOcc = new HashMap<>();
storeEle(head1, head2, eleOcc);
Node intersection_list = getIntersection(eleOcc);
Node union_list = getUnion(eleOcc);
System.out.println("\nIntersection list is: ");
printList(intersection_list);
System.out.println("\nUnion list is: ");
printList(union_list);
}
//Function to get the intersection of
//two linked lists head1 and head2
static Node getIntersection(Map<Integer, Integer> eleOcc)
{
Node result = null;
// Push a node with an element
// having occurrence of 2 as that
// means the current element is
// present in both the lists
for (int key:eleOcc.keySet()){
if(eleOcc.get(key)==2){
Node node = new Node(key);
node.next=result;
result=node;
}
}
// return resultant list
return result;
}
//Driver program to test above function
public static void main (String[] args) {
/* Start with the empty list */
LinkedList l1 = new LinkedList();
LinkedList l2 = new LinkedList();
/*create a linked list 11->10->15->4->20 */
l1.push(1);
l1.push(2);
l1.push(3);
l1.push(4);
l1.push(5);
/*create a linked list 8->4->2->10 */
l2.push(1);
l2.push(3);
l2.push(5);
l2.push(6);
System.out.print("First List: \n");
printList(l1.head);
System.out.println("\nSecond List: ");
printList(l2.head);
printUnionIntersection(l1.head, l2.head);
}
}
//Link list node
class Node{
int data;
Node next;
Node(int d){
this.data=d;
}
}
//Utility class to create a linked list
class LinkedList{
Node head;
//A utility function to insert a node at the
//beginning of a linked list
void push(int new_data){
//allocate node and put in the data
Node new_node = new Node(new_data);
//link the old list off the new node
new_node.next = head;
//move the head to point to the new node
head=new_node;
}
}
//This code is contributed by shruti456rawal
Python3
# Python code for finding union and intersection of linkedList
class linkedList:
def __init__(self):
self.head = None
self.tail = None
def insert(self, data):
if self.head is None:
self.head = Node(data)
self.tail = self.head
else:
self.tail.next = Node(data)
self.tail = self.tail.next
class Node:
def __init__(self, data):
self.data = data
self.next = None
# return the head of new list containing the intersection of 2 linkedList
def findIntersection(head1, head2):
# creating a map
hashmap = {}
# traversing on first list
while(head1 != None):
data = head1.data
if(data not in hashmap.keys()):
hashmap[data] = 1
head1 = head1.next
# making a new linkedList
ans = linkedList()
while(head2 != None):
data = head2.data
if(data in hashmap.keys()):
# adding data to new list
ans.insert(data)
head2 = head2.next
return ans.head
# return the head of new list containing the union of 2 linkedList
def union(head1, head2):
# creating a map
hashmap = {}
# traversing on first list
while(head1 != None):
data = head1.data
if(data not in hashmap.keys()):
hashmap[data] = 1
head1 = head1.next
while(head2 != None):
data = head2.data
if(data not in hashmap.keys()):
hashmap[data] = 1
head2 = head2.next
# making a new linkedList
ans = linkedList()
# traverse on hashmap
for key, value in hashmap.items():
ans.insert(key)
return ans.head
def printList(head):
while head:
print(head.data, end=' ')
head = head.next
print()
if __name__ == '__main__':
# first list
ll1 = linkedList()
ll1.insert(1)
ll1.insert(2)
ll1.insert(3)
ll1.insert(4)
ll1.insert(5)
# second list
ll2 = linkedList()
ll2.insert(1)
ll2.insert(3)
ll2.insert(5)
ll2.insert(6)
print("First list is ")
printList(ll1.head)
print("Second list is ")
printList(ll2.head)
print("Intersection list is")
printList(findIntersection(ll1.head, ll2.head))
print("Union list is ")
printList(union(ll1.head, ll2.head))
# This code is contributed by Arpit Jain
Producción:
First list is 5 4 3 2 1 Second list is 6 5 3 1 Intersection list is 3 5 1 Union list is 3 4 6 5 2 1
También podemos manejar el caso de duplicados manteniendo hash separados para ambas listas. Análisis de Complejidad:
- Complejidad Temporal: O(m+n). Aquí ‘m’ y ‘n’ son el número de elementos presentes en la primera y segunda lista respectivamente. Razón: Para Unión: Recorra ambas listas, almacene los elementos en Hash-map y actualice el conteo respectivo. Para la intersección: verifique si el recuento de un elemento en el mapa hash es ‘2’.
- Espacio Auxiliar: O(m+n). Uso de la estructura de datos Hash-map para almacenar valores.
Este artículo es una contribución de Sahil Chhabra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 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