Programa C++ para mover todas las apariciones de un elemento para terminar en una lista vinculada

Dada una lista enlazada y una clave en ella, la tarea es mover todas las apariciones de la clave dada al final de la lista enlazada, manteniendo igual el orden de todos los demás elementos.

Ejemplos:  

Input  : 1 -> 2 -> 2 -> 4 -> 3
         key = 2 
Output : 1 -> 4 -> 3 -> 2 -> 2

Input  : 6 -> 6 -> 7 -> 6 -> 3 -> 10
         key = 6
Output : 7 -> 3 -> 10 -> 6 -> 6 -> 6

Una solución simple es encontrar una por una todas las apariciones de una clave dada en la lista enlazada. Para cada ocurrencia encontrada, insértela al final. Lo hacemos hasta que todas las apariciones de la clave dada se muevan al final.

Complejidad temporal: O(n 2 )

Solución eficiente 1: es mantener dos punteros: 
pCrawl => Puntero para recorrer toda la lista uno por uno. 
pKey => Puntero a una ocurrencia de la clave si se encuentra una clave. De lo contrario, igual que pCrawl.
Comenzamos los dos punteros anteriores desde el encabezado de la lista enlazada. Movemos pKey solo cuando pKey no apunta a una tecla. Siempre movemos pCrawl . Entonces, cuando pCrawl y pKey no son lo mismo, debemos haber encontrado una clave que se encuentra antes de pCrawl , por lo que intercambiamos entre pCrawl y pKey , y movemos pKeya la siguiente ubicación. El ciclo invariable es que, después del intercambio de datos, todos los elementos desde pKey hasta pCrawl son claves.

A continuación se muestra la implementación de este enfoque.  

C++

// C++ program to move all occurrences of a
// given key to end.
#include <bits/stdc++.h>
 
// A Linked list Node
struct Node {
    int data;
    struct Node* next;
};
 
// A utility function to create a new node.
struct Node* newNode(int x)
{
    Node* temp = new Node;
    temp->data = x;
    temp->next = NULL;
}
 
// Utility function to print the elements
// in Linked list
void printList(Node* head)
{
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("
");
}
 
// Moves all occurrences of given key to
// end of linked list.
void moveToEnd(Node* head, int key)
{
    // Keeps track of locations where key
    // is present.
    struct Node* pKey = head;
 
    // Traverse list
    struct Node* pCrawl = head;
    while (pCrawl != NULL) {
        // If current pointer is not same as pointer
        // to a key location, then we must have found
        // a key in linked list. We swap data of pCrawl
        // and pKey and move pKey to next position.
        if (pCrawl != pKey && pCrawl->data != key) {
            pKey->data = pCrawl->data;
            pCrawl->data = key;
            pKey = pKey->next;
        }
 
        // Find next position where key is present
        if (pKey->data != key)
            pKey = pKey->next;
 
        // Moving to next Node
        pCrawl = pCrawl->next;
    }
}
 
// Driver code
int main()
{
    Node* head = newNode(10);
    head->next = newNode(20);
    head->next->next = newNode(10);
    head->next->next->next = newNode(30);
    head->next->next->next->next = newNode(40);
    head->next->next->next->next->next = newNode(10);
    head->next->next->next->next->next->next = newNode(60);
 
    printf("Before moveToEnd(), the Linked list is
");
    printList(head);
 
    int key = 10;
    moveToEnd(head, key);
 
    printf("
After moveToEnd(), the Linked list is
");
    printList(head);
 
    return 0;
}

Producción: 

Before moveToEnd(), the Linked list is
10 20 10 30 40 10 60 

After moveToEnd(), the Linked list is
20 30 40 60 10 10 10

Complejidad de tiempo: O (n) requiere solo un recorrido de la lista.

Solución eficiente 2: 
1. Recorra la lista enlazada y tome un puntero en la cola. 
2. Ahora, busque la clave y el Node->datos. Si son iguales, mueva el Node al último-siguiente, de lo contrario avance.

C++

// C++ code to remove key element to end of linked list
#include<bits/stdc++.h>
using namespace std;
 
// A Linked list Node
struct Node
{
    int data;
    struct Node* next;
};
 
// A utility function to create a new node.
struct Node* newNode(int x)
{
    Node* temp = new Node;
    temp->data = x;
    temp->next = NULL;
}
 
// Function to remove key to end
Node *keyToEnd(Node* head, int key)
{
 
    // Node to keep pointing to tail
    Node* tail = head;
    if (head == NULL)
    {
        return NULL;
    }
    while (tail->next != NULL)
    {
        tail = tail->next;
    }
     
    // Node to point to last of linked list
    Node* last = tail;
    Node* current = head;
    Node* prev = NULL;
     
    // Node prev2 to point to previous when head.data!=key
    Node* prev2 = NULL;
     
    // loop to perform operations to remove key to end
    while (current != tail)
    {
        if (current->data == key && prev2 == NULL)
        {
            prev = current;
            current = current->next;
            head = current;
            last->next = prev;
            last = last->next;
            last->next = NULL;
            prev = NULL;
        }
        else
        {
            if (current->data == key && prev2 != NULL)
            {
                prev = current;
                current = current->next;
                prev2->next = current;
                last->next = prev;
                last = last->next;
                last->next = NULL;
            }
            else if (current != tail)
            {
                prev2 = current;
                current = current->next;
            }
        }
    }
    return head;
}
 
// Function to display linked list
void printList(Node* head)
{
    struct Node* temp = head;
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
 
 
// Driver Code
int main()
{
    Node* root = newNode(5);
    root->next = newNode(2);
    root->next->next = newNode(2);
    root->next->next->next = newNode(7);
    root->next->next->next->next = newNode(2);
    root->next->next->next->next->next = newNode(2);
    root->next->next->next->next->next->next = newNode(2);
 
    int key = 2;
    cout << "Linked List before operations :";
    printList(root);
    cout << "\nLinked List after operations :";
    root = keyToEnd(root, key);
    printList(root);
    return 0;
}
 
// This code is contributed by Rajout-Ji

Producción: 

Linked List before operations :
5 2 2 7 2 2 2 
Linked List after operations :
5 7 2 2 2 2 2

Complejidad de tiempo: O(n), donde n representa el tamaño de la lista dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
 

Gracias a Ravinder Kumar por sugerir este método.

Solución eficiente 3: es mantener una lista separada de claves. Inicializamos esta lista de claves como vacía. Recorremos la lista dada. Por cada clave encontrada, la eliminamos de la lista original y la insertamos en una lista separada de claves. Finalmente vinculamos la lista de claves al final de la lista restante. La complejidad temporal de esta solución también es O(n) y también requiere solo un recorrido de la lista.

Consulte el artículo completo sobre Mover todas las apariciones de un elemento para terminar en una lista vinculada 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 *