Dadas dos listas enlazadas, su tarea es completar la función make union(), que devuelve la unión de dos listas enlazadas. Esta unión debe incluir sólo todos los elementos distintos. La nueva lista formada debe estar en orden no decreciente.
Input: L1 = 9->6->4->2->3->8
L2 = 1->2->8->6->2
Output: 1 2 3 4 6 8 9
Acercarse:
Hay dos tipos de montón, como todos sabemos, que es el montón mínimo y el montón máximo.
- Montón mínimo: almacena todos los elementos en orden ascendente
- Montón máximo: almacena todos los elementos en orden descendente
Primero visualicemos usando min heap para interpretar la ejecución del programa cómo se lleva a cabo la unión de dos listas vinculadas, por lo que tenemos dos operaciones como se enumeran para visualizar:
- Inserción
- Eliminación
Inserción: Después de insertar todos los elementos distintos de dos listas enlazadas,
Eliminación: eliminar la raíz hasta que minheap esté vacío
Eliminando la raíz con valor 1:
Eliminando la raíz con valor 2:
Eliminando la raíz con valor 3:
Eliminando la raíz con valor 4:
Eliminando la raíz con valor 6:
Eliminando la raíz con valor 8:
Eliminando la raíz con valor 9:
Por lo tanto, podemos concluir que en el montón mínimo, el elemento más pequeño estará en la raíz del montón, y en el montón máximo, el elemento más grande estará en la raíz del montón. Al implementar la función remove() en el montón, se eliminará el elemento raíz. Dado que la salida debe estar en orden creciente, se puede usar el montón mínimo. Priority Queue se usa para implementar un montón mínimo en Java.
Ejemplo
Java
// JAva Program toIllustrate Union of Two Linked Lists
// Using Priority Queue
// Importing basic required classes
import java.io.*;
import java.util.*;
// Class 1
// Helper class
// Node creation
class Node {
// Data and addressing variable of node
int data;
Node next;
// Constructor to initialize node
Node(int a)
{
data = a;
next = null;
}
}
// Class 2
// Main class
public class GfG {
// Reading input via Scanner class
static Scanner sc = new Scanner(System.in);
// Method 1
// To create the input list1
public static Node inputList1()
{
// Declaring node variables that is
// Head and tail
Node head, tail;
// Custom input node elements
head = tail = new Node(9);
tail.next = new Node(6);
// Fetching for next node
// using next() method
tail = tail.next;
// Similarly for node 3
tail.next = new Node(4);
tail = tail.next;
// Similarly for node 4
tail.next = new Node(2);
tail = tail.next;
// Similarly for node 5
tail.next = new Node(3);
tail = tail.next;
// Similarly for node 6
tail.next = new Node(8);
tail = tail.next;
// Returning the head
return head;
}
// Method 2
// To create the input List2
// Similar to method 1 but for List2
public static Node inputList2()
{
Node head, tail;
head = tail = new Node(1);
tail.next = new Node(2);
tail = tail.next;
tail.next = new Node(8);
tail = tail.next;
tail.next = new Node(6);
tail = tail.next;
tail.next = new Node(2);
tail = tail.next;
return head;
}
// Method 3
// To print the union list
public static void printList(Node n)
{
// Till there is a node
// condition holds true
while (n != null) {
// Print the node
System.out.print(n.data + " ");
// Moving onto next node
n = n.next;
}
}
// Method 4
// main driver method
public static void main(String args[])
{
// Taking input for List 1 and List 2
Node head1 = inputList1();
Node head2 = inputList2();
// Calling
Union obj = new Union();
printList(obj.findUnion(head1, head2));
}
}
// Class 3
// To make the union of two linked list
class Union {
public static Node findUnion(Node head1, Node head2)
{
// Creating a priority queue where
// declaring elements of integer type
PriorityQueue<Integer> minheap
= new PriorityQueue<Integer>();
// Setting heads
Node l1 = head1, l2 = head2;
// For List 1
// Inserting elements from linked list1 into
// priority queue
while (l1 != null) {
if (!minheap.contains(l1.data)) {
minheap.add(l1.data);
}
// Move to next element
l1 = l1.next;
}
// For List 2
// Inserting elements from linked list2 into
// priority queue
while (l2 != null) {
if (!minheap.contains(l2.data)) {
minheap.add(l2.data);
}
// Move to next element
l2 = l2.next;
}
Node union = new Node(0), start = union;
// Removing until heap is empty
while (!minheap.isEmpty()) {
Node temp = new Node(minheap.remove());
// Using temp to store start
start.next = temp;
start = start.next;
}
// Returning node
return union.next;
}
}
1 2 3 4 6 8 9
Complejidad de tiempo: O(nlogn), Complejidad de espacio: O(n)
Publicación traducida automáticamente
Artículo escrito por aishwaryasum y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA