Programa C++ para fusionar tipos de listas enlazadas

A menudo se prefiere la ordenación por combinación para ordenar una lista vinculada. El lento rendimiento de acceso aleatorio de una lista enlazada hace que algunos otros algoritmos (como la ordenación rápida) funcionen mal y otros (como la ordenación heap) sean completamente imposibles. 

Deje que head sea el primer Node de la lista enlazada que se ordenará y headRef sea el puntero a head. Tenga en cuenta que necesitamos una referencia al encabezado en MergeSort() ya que la implementación a continuación cambia los siguientes enlaces para ordenar las listas vinculadas (no los datos en los Nodes), por lo que el Node principal debe cambiarse si los datos en el encabezado original no son los valor más pequeño en la lista enlazada. 

MergeSort(headRef)
1) If the head is NULL or there is only one element in the Linked 
   List then return.
2) Else divide the linked list into two halves.  
      FrontBackSplit(head, &a, &b); /* a and b are two halves */
3) Sort the two halves a and b.
      MergeSort(a);
      MergeSort(b);
4) Merge the sorted a and b (using SortedMerge() discussed here) 
   and update the head pointer using headRef.
     *headRef = SortedMerge(a, b);

// C++ code for linked list merged sort
#include <bits/stdc++.h>
using namespace std;
  
// Link list node 
class Node 
{
    public:
    int data;
    Node* next;
};
  
// Function prototypes 
Node* SortedMerge(Node* a, 
                  Node* b);
void FrontBackSplit(Node* source,
                    Node** frontRef, 
                    Node** backRef);
  
// Sorts the linked list by changing 
// next pointers (not data) 
void MergeSort(Node** headRef)
{
    Node* head = *headRef;
    Node* a;
    Node* b;
  
    // Base case -- length 0 or 1 
    if ((head == NULL) || 
        (head->next == NULL)) 
    {
        return;
    }
  
    /* Split head into 'a' and 'b' 
       sublists */
    FrontBackSplit(head, &a, &b);
  
    // Recursively sort the sublists 
    MergeSort(&a);
    MergeSort(&b);
  
    /* answer = merge the two sorted 
       lists together */
    *headRef = SortedMerge(a, b);
}
  
/* See https:// www.geeksforgeeks.org/?p=3622 
   for details of this function */
Node* SortedMerge(Node* a, Node* b)
{
    Node* result = NULL;
  
    // Base cases 
    if (a == NULL)
        return (b);
    else if (b == NULL)
        return (a);
  
    /* Pick either a or b, and 
       recur */
    if (a->data <= b->data) 
    {
        result = a;
        result->next = 
                SortedMerge(a->next, b);
    }
    else 
    {
        result = b;
        result->next = 
                SortedMerge(a, b->next);
    }
    return (result);
}
  
// UTILITY FUNCTIONS 
/* Split the nodes of the given list into 
   front and back halves, and return the two 
   lists using the reference parameters. If 
   the length is odd, the extra node should 
   go in the front list. Uses the fast/slow 
   pointer strategy. */
void FrontBackSplit(Node* source,
                    Node** frontRef, 
                    Node** backRef)
{
    Node* fast;
    Node* slow;
    slow = source;
    fast = source->next;
  
    /* Advance 'fast' two nodes, and 
       advance 'slow' one node */
    while (fast != NULL) 
    {
        fast = fast->next;
        if (fast != NULL) 
        {
            slow = slow->next;
            fast = fast->next;
        }
    }
  
    /* 'slow' is before the midpoint in 
        the list, so split it in two at 
        that point. */
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
}
  
/* Function to print nodes in a 
   given linked list */
void printList(Node* node)
{
    while (node != NULL) 
    {
        cout << node->data << " ";
        node = node->next;
    }
}
  
/* Function to insert a node at the 
   beginning of the linked list */
void push(Node** head_ref, int new_data)
{
    // Allocate node 
    Node* new_node = new Node();
  
    // Put in the data 
    new_node->data = new_data;
  
    // Link the old list off the 
    // new node 
    new_node->next = (*head_ref);
  
    // Move the head to point to 
    // the new node 
    (*head_ref) = new_node;
}
  
// Driver code
int main()
{
    // Start with the empty list 
    Node* res = NULL;
    Node* a = NULL;
  
    /* Let us create a unsorted linked lists 
       to test the functions created lists shall 
       be a: 2->3->20->5->10->15 */
    push(&a, 15);
    push(&a, 10);
    push(&a, 5);
    push(&a, 20);
    push(&a, 3);
    push(&a, 2);
  
    // Sort the above created Linked List 
    MergeSort(&a);
  
    cout << "Sorted Linked List is: ";
    printList(a);
  
    return 0;
}
// This is code is contributed by rathbhupendra

Producción:

Sorted Linked List is: 
2 3 5 10 15 20

Complejidad de tiempo: O(n*log n)

Complejidad espacial: O(n*log n)

Enfoque 2: este enfoque es más simple y utiliza el espacio log n.

mergeSort():

1. Si el tamaño de la lista enlazada es 1, devuelve la cabeza
2. Encuentre medio usando el enfoque de la Turtle y la liebre
3. Guarde el siguiente de mid en head2, es decir, la lista de subenlaces correctos.
4. Ahora haz que el siguiente punto medio sea nulo.
5. Llame recursivamente a mergeSort() en la lista subvinculada izquierda y derecha y almacene el nuevo encabezado de la lista vinculada izquierda y derecha.
6. Llame a merge() dados los argumentos nuevos encabezados de listas subvinculadas izquierda y derecha y almacene el encabezado final devuelto después de la fusión.
7. Devuelve el encabezado final de la lista enlazada fusionada.

fusionar (cabeza1, cabeza2):

1. Tome un puntero, digamos fusionado, para almacenar la lista fusionada en él y almacene un Node ficticio en él.
2. Tome una temperatura de puntero y asígnele fusionar.
3. Si los datos de head1 son menores que los datos de head2, entonces, almacene head1 en el siguiente de temp y mueva head1 al siguiente de head1.
4. De lo contrario, almacene head2 en el siguiente de temp y mueva head2 al siguiente de head2.
5. Mover temp al siguiente de temp.
6. Repita los pasos 3, 4 y 5 hasta que head1 no sea igual a nulo y head2 no sea igual a nulo.
7. Ahora agregue los Nodes restantes de la primera o la segunda lista vinculada a la lista vinculada fusionada.
8. Devuelve el siguiente de fusionado (que ignorará el maniquí y devolverá el encabezado de la lista enlazada fusionada final)

// C++ program to implement
// the above approach
#include<iostream>
using namespace std;
  
// Node structure
struct Node
{
    int data;
    Node *next;
};
  
// Function to insert in list
void insert(int x, Node **head) 
{
    if(*head == NULL)
    {
        *head = new Node;
        (*head)->data = x;
        (*head)->next = NULL;
        return;
    }
  
    Node *temp = new Node;
    temp->data = (*head)->data;
    temp->next = (*head)->next;
    (*head)->data = x;
    (*head)->next = temp;
}
  
// Function to print the list
void print(Node *head) 
{
    Node *temp = head;
    while(temp != NULL) 
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
}
  
Node *merge(Node *firstNode,
            Node *secondNode) 
{
    Node *merged = new Node;
    Node *temp = new Node;
     
    // Merged is equal to temp so in the 
    // end we have the top Node.
    merged = temp;
  
    // while either firstNode or secondNode 
    // becomes NULL
    while(firstNode != NULL && 
          secondNode != NULL) 
    {    
        if(firstNode->data <= 
           secondNode->data) 
        {
            temp->next = firstNode;
            firstNode = firstNode->next;
        }
          
        else 
        {
            temp->next = secondNode;
            secondNode = secondNode->next;
        }
        temp = temp->next;
    }
     
   // Any remaining Node in firstNode or 
   // secondNode gets inserted in the temp 
   // List
    while(firstNode!=NULL) 
    {
        temp->next = firstNode;
        firstNode = firstNode->next;
        temp = temp->next;
    }
  
    while(secondNode!=NULL) 
    {
        temp->next = secondNode;
        secondNode = secondNode->next;
        temp = temp->next;
    }
  
    // Return the head of the sorted list
    return merged->next;
}
  
// Function to calculate the middle 
// Element
Node *middle(Node *head) 
{
    Node *slow = head;
    Node *fast = head->next;
     
    while(slow->next != NULL && 
         (fast!=NULL && fast->next!=NULL)) 
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
  
// Function to sort the given list
Node *sort(Node *head)
{    
    if(head->next == NULL) 
    {
        return head;
    }
  
    Node *mid = new Node;
    Node *head2 = new Node;
    mid = middle(head);
    head2 = mid->next;   
    mid->next = NULL;
      
    // Recursive call to sort() hence diving 
    // our problem, and then merging the solution
    Node *finalhead = merge(sort(head),
                            sort(head2));  
    return finalhead;
}
  
int main(void) 
{
    Node *head = NULL;
    int n[] = {7, 10, 5, 20, 3, 2};
    for(int i = 0; i < 6; i++) 
    {
        // Inserting in the list
        insert(n[i], &head);   
    }
  
    cout << "Sorted Linked List is: ";
  
    // Printing the sorted list returned 
    // by sort()
    print(sort(head));     
    return 0;
}

Producción:

Sorted Linked List is: 
2 3 5 7 10 20 

Complejidad del tiempo : O(n*log n)

Complejidad espacial: O(log n)

¡Consulte el artículo completo sobre Merge Sort para listas vinculadas para obtener más detalles!