Programa C para clasificación de combinación para lista doblemente enlazada

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<stdio.h>
#include<stdlib.h>
struct Node
{
    int data;
    struct Node *next, *prev;
};
  
struct Node *split(struct Node *head);
  
// Function to merge two linked lists
struct Node *merge(struct Node *first, 
                   struct 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
struct Node *mergeSort(struct Node *head)
{
    if (!head || !head->next)
        return head;
    struct 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(struct Node **head, int data)
{
    struct Node *temp =
    (struct Node *)malloc(sizeof(struct 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(struct Node *head)
{
    struct Node *temp = head;
    printf(
    "Forward Traversal using next pointer");
  
    while (head)
    {
        printf("%d ",head->data);
        temp = head;
        head = head->next;
    }
    printf(
    "Backward Traversal using prev pointer");
    while (temp)
    {
        printf("%d ", 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
struct Node *split(struct Node *head)
{
    struct Node *fast = head,*slow = head;
    while (fast->next && fast->next->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    struct Node *temp = slow->next;
    slow->next = NULL;
    return temp;
}
  
// Driver program
int main(void)
{
    struct Node *head = NULL;
    insert(&head,5);
    insert(&head,20);
    insert(&head,4);
    insert(&head,3);
    insert(&head,30);
    insert(&head,10);
    head = mergeSort(head);
    printf(
    "Linked List after sorting");
    print(head);
    return 0;
}

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *