Dada una lista doblemente enlazada, escribe una función para ordenar la lista doblemente enlazada en orden creciente usando la ordenación por combinación.
Por ejemplo, la siguiente lista doblemente enlazada debe cambiarse a 24810
Ya se ha discutido la ordenación por combinación para la lista enlazada individualmente . El cambio importante aquí es modificar los punteros anteriores también al fusionar dos listas.
A continuación se muestra la implementación de la ordenación por fusión para la lista doblemente enlazada.
C++
// C++ program for merge sort on doubly
// linked list
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node *next, *prev;
};
Node *split(Node *head);
// Function to merge two linked lists
Node *merge(Node *first, Node *second)
{
// If first linked list is empty
if (!first)
return second;
// If second linked list is empty
if (!second)
return first;
// Pick the smaller value
if (first->data < second->data)
{
first->next = merge(first->next,
second);
first->next->prev = first;
first->prev = NULL;
return first;
}
else
{
second->next = merge(first,second->next);
second->next->prev = second;
second->prev = NULL;
return second;
}
}
// Function to do merge sort
Node *mergeSort(Node *head)
{
if (!head || !head->next)
return head;
Node *second = split(head);
// Recur for left and right halves
head = mergeSort(head);
second = mergeSort(second);
// Merge the two sorted halves
return merge(head,second);
}
// A utility function to insert a new node
// at the beginning of doubly linked list
void insert(Node **head, int data)
{
Node *temp = new Node();
temp->data = data;
temp->next = temp->prev = NULL;
if (!(*head))
(*head) = temp;
else
{
temp->next = *head;
(*head)->prev = temp;
(*head) = temp;
}
}
// A utility function to print a doubly
// linked list in both forward and
// backward directions
void print(Node *head)
{
Node *temp = head;
cout <<
"Forward Traversal using next pointer";
while (head)
{
cout << head->data << " ";
temp = head;
head = head->next;
}
cout <<
"Backward Traversal using prev pointer";
while (temp)
{
cout << temp->data << " ";
temp = temp->prev;
}
}
// Utility function to swap two integers
void swap(int *A, int *B)
{
int temp = *A;
*A = *B;
*B = temp;
}
// Split a doubly linked list (DLL) into
// 2 DLLs of half sizes
Node *split(Node *head)
{
Node *fast = head,*slow = head;
while (fast->next && fast->next->next)
{
fast = fast->next->next;
slow = slow->next;
}
Node *temp = slow->next;
slow->next = NULL;
return temp;
}
// Driver program
int main(void)
{
Node *head = NULL;
insert(&head, 5);
insert(&head, 20);
insert(&head, 4);
insert(&head, 3);
insert(&head, 30);
insert(&head, 10);
head = mergeSort(head);
cout << "Linked List after sorting";
print(head);
return 0;
}
// This is code is contributed by rathbhupendra
Producción:
Linked List after sorting Forward Traversal using next pointer 3 4 5 10 20 30 Backward Traversal using prev pointer 30 20 10 5 4 3
Complejidad de tiempo: la complejidad de tiempo de la implementación anterior es la misma que la complejidad de tiempo de MergeSort para arrays . Toma tiempo Θ(nLogn).
Complejidad espacial: O(1). Solo estamos usando una cantidad constante de espacio extra.
También le puede interesar ver QuickSort para la lista doblemente enlazada.
Consulte el artículo completo sobre Merge Sort para la lista doblemente enlazada para obtener más detalles.
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