Dada una lista enlazada donde cada Node representa una lista enlazada y contiene dos punteros de su tipo:
- Puntero al siguiente Node en la lista principal (lo llamamos puntero ‘derecho’ en el siguiente código)
- Puntero a una lista vinculada donde este Node es la cabeza (lo llamamos puntero ‘abajo’ en el código a continuación).
Todas las listas enlazadas están ordenadas. Ver el siguiente ejemplo
Ejemplos:
Input: 5 -> 10 -> 19 -> 28 | | | | V V V V 7 20 22 35 | | | V V V 8 50 40 | | V V 30 45 Output: 5->7->8->10->19->20->22->28->30->35->40->45->50 Input: 5 -> 10 -> 19 -> 28 | | V V 7 22 | | V V 8 50 | V 30 Output: 5->7->8->10->19->20->22->30->50
En la publicación anterior , tenemos que usar el proceso merge() de clasificación por fusión para listas vinculadas para aplanar la lista vinculada.
En esta publicación, lo resolveremos usando Heap .
Enfoque: La idea es observar que de cada Node superior hay N Nodes que están conectados en dirección hacia abajo, pero observe que todos los Nodes hacia abajo están ordenados. Entonces, la tarea es ordenar todo esto en orden creciente (o decreciente).
- Empuje la cabeza de todas las listas vinculadas en la lista hacia abajo en la cola de prioridad .
- Extraiga el Node más pequeño de la cola de prioridad.
- Verifique la ubicación del Node para que el siguiente Node apuntado por el Node actual pueda ser empujado a la cola de prioridad.
- Nuevamente extraiga el elemento más pequeño e inserte el siguiente Node apuntado por el Node actual hasta que el montón se vacíe.
- Continúe agregando los datos de los Nodes en una nueva lista vinculada que aparece en la nueva lista.
- Imprima la lista enlazada formada arriba.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for Flattening
// a linked list using Heaps
#include <bits/stdc++.h>
using namespace std;
// Structure of given Linked list
struct Node {
int data;
struct Node* right;
struct Node* down;
Node(int x)
{
data = x;
right = NULL;
down = NULL;
}
};
// Function to print the
// linked list
void printList(Node* Node)
{
while (Node != NULL) {
printf("%d ", Node->data);
Node = Node->down;
}
}
// Function that compares the value
// pointed by node and returns true
// if first data is greater
struct compare {
bool operator()(Node* a, Node* b)
{
return a->data > b->data;
}
};
// Function which returns the root
// of the flattened linked list
Node* flatten(Node* root)
{
Node* ptr = root;
Node* head = NULL;
// Min Heap which will return
// smallest element currently
// present in heap
priority_queue<Node*,
vector<Node*>,
compare> pq;
// Push the head nodes of each
// downward linked list
while (ptr != NULL) {
pq.push(ptr);
ptr = ptr->right;
}
// This loop will execute
// till the map becomes empty
while (!pq.empty()) {
// Pop out the node that
// contains element
// currently in heap
Node* temp = pq.top();
pq.pop();
// Push the next node pointed by
// the current node into heap
// if it is not null
if (temp->down != NULL) {
pq.push(temp->down);
}
// Create new linked list
// that is to be returned
if (head == NULL) {
head = temp;
ptr = temp;
ptr->right = NULL;
}
else {
ptr->down = temp;
ptr = temp;
ptr->right = NULL;
}
}
// Pointer to head node
// in the linked list
return head;
}
// Create and push new nodes
void push(Node** head_ref, int new_data)
{
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->right = NULL;
new_node->data = new_data;
new_node->down = (*head_ref);
(*head_ref) = new_node;
}
// Driver Code
int main()
{
Node* root = NULL;
// Given Linked List
push(&root, 30);
push(&root, 8);
push(&root, 7);
push(&root, 5);
push(&(root->right), 20);
push(&(root->right), 10);
push(&(root->right->right), 50);
push(&(root->right->right), 22);
push(&(root->right->right), 19);
push(&(root->right->right->right), 45);
push(&(root->right->right->right), 40);
push(&(root->right->right->right), 35);
push(&(root->right->right->right), 20);
// Flatten the list
root = flatten(root);
// Print the flattened linked list
printList(root);
return 0;
}
Java
// Java program for Flattening
// a linked list using Heaps
import java.util.*;
// Linked list Node
class Node {
int data;
Node right, down;
Node(int data)
{
this.data = data;
right = null;
down = null;
}
}
class pair {
int val;
Node head;
pair(Node head, int val)
{
this.val = val;
this.head = head;
}
}
// Class that compares the value
// pointed by node and make
// LinkedList sorted
class pairComp implements Comparator<pair> {
public int compare(pair p1, pair p2)
{
return p1.val - p2.val;
}
}
class GFG {
// Function which returns the root
// of the flattened linked list
public static Node flatten(Node root)
{
Node ptr = root;
Node h = null;
// Min Heap which will return
// smallest element currently
// present in heap
PriorityQueue<pair> pq
= new PriorityQueue<pair>(
new pairComp());
// Push the head nodes of each
// downward linked list
while (ptr != null) {
pq.add(new pair(ptr, ptr.data));
ptr = ptr.right;
}
// This loop will execute
// till the pq becomes empty
while (!pq.isEmpty()) {
// Pop out the node that
// contains element
// currently in heap
Node temp = pq.poll().head;
// Push the next node pointed by
// the current node into heap
// if it is not null
if (temp.down != null) {
pq.add(new pair(temp.down,
temp.down.data));
}
// Create new linked list
// that is to be returned
if (h == null) {
h = temp;
ptr = temp;
ptr.right = null;
}
else {
ptr.down = temp;
ptr = temp;
ptr.right = null;
}
}
// Pointer to head node
// in the linked list
return h;
}
// Create and push new nodes
public static Node push(Node head_ref,
int data)
{
// Allocate the Node &
// Put in the data
Node new_node = new Node(data);
// Make next of new Node as head
new_node.down = head_ref;
// Move the head to point to new Node
head_ref = new_node;
// return to link it back
return head_ref;
}
// Function to print the
// linked list
public static void printList(Node h)
{
while (h != null) {
System.out.print(h.data + " ");
h = h.down;
}
}
// Driver code
public static void main(String args[])
{
Node head = null;
head = push(head, 30);
head = push(head, 8);
head = push(head, 7);
head = push(head, 5);
head.right = push(head.right, 20);
head.right = push(head.right, 10);
head.right.right = push(
head.right.right, 50);
head.right.right = push(
head.right.right, 22);
head.right.right = push(
head.right.right, 19);
head.right.right.right
= push(
head.right.right.right, 45);
head.right.right.right
= push(
head.right.right.right, 40);
head.right.right.right
= push(
head.right.right.right, 35);
head.right.right.right
= push(head.right.right.right, 20);
// Flatten the list
head = flatten(head);
printList(head);
}
}
// This code is contributed by Naresh Saharan
// and Sagar Jangra and Tridib Samanta
Producción
5 7 8 10 19 20 20 22 30 35 40 45 50
Complejidad de tiempo: O(k * log k) + O((Nk) * log k) = O(N * log k) , donde ‘ k ‘ es el número de Nodes en la lista enlazada horizontal superior y ‘ N ‘ es el número total de Nodes entre todas las listas enlazadas. Se toma el tiempo ‘ log k ‘ para el procedimiento min-heapify.
Espacio auxiliar: O(k) para el montón mínimo, donde ‘ k ‘ es el número de Nodes en la lista enlazada horizontal superior. El montón mínimo tendrá como máximo ‘ k ‘ número de Nodes en cualquier momento.