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 código a continuación)
- Puntero a una lista vinculada a la que se dirige este Node (lo llamamos el puntero ‘abajo’ en el código a continuación).
Todas las listas enlazadas están ordenadas. Ver el siguiente ejemplo
5 -> 10 -> 19 -> 28
| | | |
V V V V
7 20 22 35
| | |
V V V
8 50 40
| |
V V
30 45
Escriba una función flatten() para aplanar las listas en una sola lista enlazada. La lista enlazada aplanada también debe ordenarse. Por ejemplo, para la lista de entrada anterior, la lista de salida debe ser 5->7->8->10->19->20->22->28->30->35->40->45->50 .
La idea es usar el proceso Merge() de clasificación por fusión para listas enlazadas. Usamos merge() para fusionar listas una por una. Fusionamos recursivamente() la lista actual con la lista ya aplanada.
El puntero hacia abajo se usa para vincular Nodes de la lista plana.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for flattening a Linked List
#include <bits/stdc++.h>
using namespace std;
// Link list node
class Node
{
public:
int data;
Node *right, *down;
};
Node* head = NULL;
// An utility function to merge two sorted
// linked lists
Node* merge(Node* a, Node* b)
{
// If first linked list is empty then second
// is the answer
if (a == NULL)
return b;
// If second linked list is empty then first
// is the result
if (b == NULL)
return a;
// Compare the data members of the two linked
// lists and put the larger one in the result
Node* result;
if (a->data < b->data)
{
result = a;
result->down = merge(a->down, b);
}
else
{
result = b;
result->down = merge(a, b->down);
}
result->right = NULL;
return result;
}
Node* flatten(Node* root)
{
// Base Cases
if (root == NULL || root->right == NULL)
return root;
// Recur for list on right
root->right = flatten(root->right);
// Now merge
root = merge(root, root->right);
// Return the root
// it will be in turn merged with its left
return root;
}
// Utility function to insert a node at
// beginning of the linked list
Node* push(Node* head_ref, int data)
{
// Allocate the Node & Put in the data
Node* new_node = new Node();
new_node->data = data;
new_node->right = NULL;
// 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 head_ref;
}
void printList()
{
Node* temp = head;
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->down;
}
cout << endl;
}
// Driver code
int main()
{
/* Let us create the following linked list
5 -> 10 -> 19 -> 28
| | | |
V V V V
7 20 22 35
| | |
V V V
8 50 40
| |
V V
30 45
*/
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();
return 0;
}
// This code is contributed by rajsanghavi9.
Java
// Java program for flattening a Linked List
class LinkedList
{
Node head; // head of list
/* Linked list Node*/
class Node
{
int data;
Node right, down;
Node(int data)
{
this.data = data;
right = null;
down = null;
}
}
// An utility function to merge two sorted linked lists
Node merge(Node a, Node b)
{
// if first linked list is empty then second
// is the answer
if (a == null) return b;
// if second linked list is empty then first
// is the result
if (b == null) return a;
// compare the data members of the two linked lists
// and put the larger one in the result
Node result;
if (a.data < b.data)
{
result = a;
result.down = merge(a.down, b);
}
else
{
result = b;
result.down = merge(a, b.down);
}
result.right = null;
return result;
}
Node flatten(Node root)
{
// Base Cases
if (root == null || root.right == null)
return root;
// recur for list on right
root.right = flatten(root.right);
// now merge
root = merge(root, root.right);
// return the root
// it will be in turn merged with its left
return root;
}
/* Utility function to insert a node at beginning of the
linked list */
Node push(Node head_ref, int data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(data);
/* 3. Make next of new Node as head */
new_node.down = head_ref;
/* 4. Move the head to point to new Node */
head_ref = new_node;
/*5. return to link it back */
return head_ref;
}
void printList()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.down;
}
System.out.println();
}
/* Driver program to test above functions */
public static void main(String args[])
{
LinkedList L = new LinkedList();
/* Let us create the following linked list
5 -> 10 -> 19 -> 28
| | | |
V V V V
7 20 22 35
| | |
V V V
8 50 40
| |
V V
30 45
*/
L.head = L.push(L.head, 30);
L.head = L.push(L.head, 8);
L.head = L.push(L.head, 7);
L.head = L.push(L.head, 5);
L.head.right = L.push(L.head.right, 20);
L.head.right = L.push(L.head.right, 10);
L.head.right.right = L.push(L.head.right.right, 50);
L.head.right.right = L.push(L.head.right.right, 22);
L.head.right.right = L.push(L.head.right.right, 19);
L.head.right.right.right = L.push(L.head.right.right.right, 45);
L.head.right.right.right = L.push(L.head.right.right.right, 40);
L.head.right.right.right = L.push(L.head.right.right.right, 35);
L.head.right.right.right = L.push(L.head.right.right.right, 20);
// flatten the list
L.head = L.flatten(L.head);
L.printList();
}
} /* This code is contributed by Rajat Mishra */
Python3
# Python program for flattening a Linked List class Node(): def __init__(self,data): self.data = data self.right = None self.down = None class LinkedList(): def __init__(self): # head of list self.head = None # Utility function to insert a node at beginning of the # linked list def push(self,head_ref,data): # 1 & 2: Allocate the Node & # Put in the data new_node = Node(data) # Make next of new Node as head new_node.down = head_ref # 4. Move the head to point to new Node head_ref = new_node # 5. return to link it back return head_ref def printList(self): temp = self.head while(temp != None): print(temp.data,end=" ") temp = temp.down print() # An utility function to merge two sorted linked lists def merge(self, a, b): # if first linked list is empty then second # is the answer if(a == None): return b # if second linked list is empty then first # is the result if(b == None): return a # compare the data members of the two linked lists # and put the larger one in the result result = None if (a.data < b.data): result = a result.down = self.merge(a.down,b) else: result = b result.down = self.merge(a,b.down) result.right = None return result def flatten(self, root): # Base Case if(root == None or root.right == None): return root # recur for list on right root.right = self.flatten(root.right) # now merge root = self.merge(root, root.right) # return the root # it will be in turn merged with its left return root # Driver program to test above functions L = LinkedList() ''' Let us create the following linked list 5 -> 10 -> 19 -> 28 | | | | V V V V 7 20 22 35 | | | V V V 8 50 40 | | V V 30 45 ''' L.head = L.push(L.head, 30); L.head = L.push(L.head, 8); L.head = L.push(L.head, 7); L.head = L.push(L.head, 5); L.head.right = L.push(L.head.right, 20); L.head.right = L.push(L.head.right, 10); L.head.right.right = L.push(L.head.right.right, 50); L.head.right.right = L.push(L.head.right.right, 22); L.head.right.right = L.push(L.head.right.right, 19); L.head.right.right.right = L.push(L.head.right.right.right, 45); L.head.right.right.right = L.push(L.head.right.right.right, 40); L.head.right.right.right = L.push(L.head.right.right.right, 35); L.head.right.right.right = L.push(L.head.right.right.right, 20); # flatten the list L.head = L.flatten(L.head); L.printList() # This code is contributed by maheshwaripiyush9
C#
// C# program for flattening a Linked List
using System;
public class List {
Node head; // head of list
/* Linked list Node */
public
class Node {
public
int data;
public
Node right, down;
public
Node(int data) {
this.data = data;
right = null;
down = null;
}
}
// An utility function to merge two sorted linked lists
Node merge(Node a, Node b) {
// if first linked list is empty then second
// is the answer
if (a == null)
return b;
// if second linked list is empty then first
// is the result
if (b == null)
return a;
// compare the data members of the two linked lists
// and put the larger one in the result
Node result;
if (a.data < b.data) {
result = a;
result.down = merge(a.down, b);
}
else {
result = b;
result.down = merge(a, b.down);
}
result.right = null;
return result;
}
Node flatten(Node root) {
// Base Cases
if (root == null || root.right == null)
return root;
// recur for list on right
root.right = flatten(root.right);
// now merge
root = merge(root, root.right);
// return the root
// it will be in turn merged with its left
return root;
}
/*
* Utility function to insert a node at beginning of the linked list
*/
Node Push(Node head_ref, int data) {
/*
* 1 & 2: Allocate the Node & Put in the data
*/
Node new_node = new Node(data);
/* 3. Make next of new Node as head */
new_node.down = head_ref;
/* 4. Move the head to point to new Node */
head_ref = new_node;
/* 5. return to link it back */
return head_ref;
}
void printList() {
Node temp = head;
while (temp != null) {
Console.Write(temp.data + " ");
temp = temp.down;
}
Console.WriteLine();
}
/* Driver program to test above functions */
public static void Main(String []args) {
List L = new List();
/*
* Let us create the following linked list 5 -> 10 -> 19 -> 28 | | | | V V V V 7
* 20 22 35 | | | V V V 8 50 40 | | V V 30 45
*/
L.head = L.Push(L.head, 30);
L.head = L.Push(L.head, 8);
L.head = L.Push(L.head, 7);
L.head = L.Push(L.head, 5);
L.head.right = L.Push(L.head.right, 20);
L.head.right = L.Push(L.head.right, 10);
L.head.right.right = L.Push(L.head.right.right, 50);
L.head.right.right = L.Push(L.head.right.right, 22);
L.head.right.right = L.Push(L.head.right.right, 19);
L.head.right.right.right = L.Push(L.head.right.right.right, 45);
L.head.right.right.right = L.Push(L.head.right.right.right, 40);
L.head.right.right.right = L.Push(L.head.right.right.right, 35);
L.head.right.right.right = L.Push(L.head.right.right.right, 20);
// flatten the list
L.head = L.flatten(L.head);
L.printList();
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// javascript program for flattening a Linked List
var head; // head of list
/* Linked list Node */
class Node {
constructor(val) {
this.data = val;
this.down = null;
this.next = null;
}
}
// An utility function to merge two sorted linked lists
function merge(a, b) {
// if first linked list is empty then second
// is the answer
if (a == null)
return b;
// if second linked list is empty then first
// is the result
if (b == null)
return a;
// compare the data members of the two linked lists
// and put the larger one in the result
var result;
if (a.data < b.data) {
result = a;
result.down = merge(a.down, b);
}
else {
result = b;
result.down = merge(a, b.down);
}
result.right = null;
return result;
}
function flatten(root) {
// Base Cases
if (root == null || root.right == null)
return root;
// recur for list on right
root.right = flatten(root.right);
// now merge
root = merge(root, root.right);
// return the root
// it will be in turn merged with its left
return root;
}
/*
* Utility function to insert a node at beginning of the linked list
*/
function push(head_ref , data) {
/*
* 1 & 2: Allocate the Node & Put in the data
*/
var new_node = new Node(data);
/* 3. Make next of new Node as head */
new_node.down = head_ref;
/* 4. Move the head to point to new Node */
head_ref = new_node;
/* 5. return to link it back */
return head_ref;
}
function printList() {
var temp = head;
while (temp != null) {
document.write(temp.data + " ");
temp = temp.down;
}
document.write();
}
/* Driver program to test above functions */
/*
* Let us create the following linked list 5 -> 10 -> 19 -> 28 | | | | V V V V 7
* 20 22 35 | | | V V V 8 50 40 | | V V 30 45
*/
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();
// This code contributed by aashish1995
</script>
Producción
5 7 8 10 19 20 20 22 30 35 40 45 50
Complejidad de tiempo: O(N*N*M) – donde N es el número de Nodes en la lista enlazada principal (accesible usando el puntero derecho) y M es el número de Node en una sola lista subvinculada (accesible usando el puntero hacia abajo).
Explicación: Como estamos fusionando 2 listas a la vez,
- Después de agregar las 2 primeras listas, el tiempo necesario será O(M+M) = O(2M).
- Luego fusionaremos otra lista con la lista fusionada anterior -> tiempo = O (2M + M) = O (3M).
- Luego fusionaremos otra lista -> tiempo = O(3M + M).
- Seguiremos fusionando listas con listas previamente fusionadas hasta que se fusionen todas las listas.
- El tiempo total empleado será O(2M + 3M + 4M + …. N*M) = (2 + 3 + 4 + … + N)*M
- Usando la fórmula de la suma aritmética: tiempo = O((N*N + N – 2)*M/2)
- La expresión anterior es aproximadamente igual a O(N*N*M) para valores grandes de N
Complejidad espacial: O(N*M) – debido a la recursividad. Las funciones recursivas usarán una pila recursiva de tamaño equivalente al número total de elementos en las listas, que es N*M.
Método 2: uso de colas de prioridad
La idea es construir min-heap y usar la propiedad Extract-min para obtener el elemento mínimo de la cola de prioridad.
C++
#include <bits/stdc++.h>
struct Node {
int data;
struct Node* next;
struct Node* bottom;
Node(int x)
{
data = x;
next = NULL;
bottom = NULL;
}
};
using namespace std;
void flatten(Node* root);
int main(void)
{
//this code builds the flattened linked list
//of first picture in this article ;
Node* head=new Node(5);
auto temp=head;
auto bt=head;
bt->bottom=new Node(7);
bt->bottom->bottom=new Node(8);
bt->bottom->bottom->bottom=new Node(30);
temp->next=new Node(10);
temp=temp->next;
bt=temp;
bt->bottom=new Node(20);
temp->next=new Node(19);
temp=temp->next;
bt=temp;
bt->bottom=new Node(22);
bt->bottom->bottom=new Node(50);
temp->next=new Node(28);
temp=temp->next;
bt=temp;
bt->bottom=new Node(35);
bt->bottom->bottom=new Node(40);
bt->bottom->bottom->bottom=new Node(45);
flatten(head);
cout << endl;
return 0;
}
struct mycomp {
bool operator()(Node* a, Node* b)
{
return a->data > b->data;
}
};
void flatten(Node* root)
{
priority_queue<Node*, vector<Node*>, mycomp> p;
//pushing main link nodes into priority_queue.
while (root!=NULL) {
p.push(root);
root = root->next;
}
while (!p.empty()) {
//extracting min
auto k = p.top();
p.pop();
//printing least element
cout << k->data << " ";
if (k->bottom)
p.push(k->bottom);
}
}
//this code is contributed by user_990i
Producción
5 7 8 10 19 20 22 28 30 35 40 45 50
Complejidad de tiempo: O(N*M*log(N)) – donde N es el número de Nodes en la lista enlazada principal (accesible usando el siguiente puntero) y M es el número de Node en una sola lista subenlazada (accesible usando el puntero inferior ).
Explicación:
1. Empuje todos los Nodes a los que se puede acceder usando el siguiente puntero en la cola de prioridad hasta que encontremos NULL .
2.while (priority_queue no está vacío )
(i) Extraiga el Node que contiene el valor mínimo (k) de la cola de prioridad e imprima k->datos .
(ii) Si k->bottom!=NULL , inserte k->bottom en la cola_prioridad. De lo contrario, el tamaño de nuestra cola de prioridad disminuirá.
Complejidad espacial: O(N) -donde N es el número de Nodes en la lista enlazada principal (accesible usando el siguiente puntero).
NOTA: En la explicación anterior, k significa el Node que contiene el elemento mínimo.
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