Programa C++ para intercambiar Nodes en una lista vinculada sin intercambiar datos

Dada una lista enlazada y dos claves en ella, intercambie Nodes por dos claves dadas. Los Nodes deben intercambiarse cambiando los enlaces. El intercambio de datos de Nodes puede ser costoso en muchas situaciones cuando los datos contienen muchos campos. 

Se puede suponer que todas las claves de la lista enlazada son distintas.

Ejemplos: 

Input : 10->15->12->13->20->14,  x = 12, y = 20
Output: 10->15->20->13->12->14

Input : 10->15->12->13->20->14,  x = 10, y = 20
Output: 20->15->12->13->10->14

Input : 10->15->12->13->20->14,  x = 12, y = 13
Output: 10->15->13->12->20->14

Esto puede parecer un problema simple, pero es una pregunta interesante ya que tiene que manejar los siguientes casos. 

1. xey pueden o no ser adyacentes.
2. Cualquiera de los dos, x o y, puede ser un Node principal.
3. O x o y puede ser el último Node.
4. x y/oy pueden no estar presentes en la lista enlazada.

Cómo escribir un código de trabajo limpio que maneje todas las posibilidades anteriores.

La idea es buscar primero x e y en la lista enlazada dada. Si alguno de ellos no está presente, entonces regrese. Mientras busca x e y, realice un seguimiento de los punteros actuales y anteriores. Primero cambie el siguiente de los punteros anteriores, luego cambie el siguiente de los punteros actuales. 

A continuación se muestra la implementación del enfoque anterior. 

// C++ program to swap the nodes of linked list rather
// than swapping the field from the nodes.
#include <bits/stdc++.h>
using namespace std;
 
// A linked list node
class Node
{
    public:
    int data;
    Node* next;
};
 
// Function to swap nodes x and y in
// linked list by changing links
void swapNodes(Node** head_ref,
               int x, int y)
{
    // Nothing to do if x and y
    // are same
    if (x == y)
        return;
 
    // Search for x (keep track of
    // prevX and CurrX
    Node *prevX = NULL,
         *currX = *head_ref;
    while (currX && currX->data != x)
    {
        prevX = currX;
        currX = currX->next;
    }
 
    // Search for y (keep track of
    // prevY and CurrY
    Node *prevY = NULL,
         *currY = *head_ref;
    while (currY && currY->data != y)
    {
        prevY = currY;
        currY = currY->next;
    }
 
    // If either x or y is not present,
    // nothing to do
    if (currX == NULL ||
        currY == NULL)
        return;
 
    // If x is not head of linked list
    if (prevX != NULL)
        prevX->next = currY;
    else
 
        // Else make y as new head
        *head_ref = currY;
 
    // If y is not head of linked list
    if (prevY != NULL)
        prevY->next = currX;
    else // Else make x as new head
        *head_ref = currX;
 
    // Swap next pointers
    Node* temp = currY->next;
    currY->next = currX->next;
    currX->next = temp;
}
 
// Function to add a node at the
// beginning of 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;
}
 
// Function to print nodes in a
// given linked list
void printList(Node* node)
{
    while (node != NULL)
    {
        cout << node->data << " ";
        node = node->next;
    }
}
 
// Driver code
int main()
{
    Node* start = NULL;
 
    /* The constructed linked list is:
       1->2->3->4->5->6->7 */
    push(&start, 7);
    push(&start, 6);
    push(&start, 5);
    push(&start, 4);
    push(&start, 3);
    push(&start, 2);
    push(&start, 1);
 
    cout << "Linked list before calling swapNodes() ";
    printList(start);
    swapNodes(&start, 4, 3);
    cout << "Linked list after calling swapNodes() ";
    printList(start);
    return 0;
}
// This is code is contributed by rathbhupendra

Producción:

Linked list before calling swapNodes() 1 2 3 4 5 6 7 
Linked list after calling swapNodes() 1 2 4 3 5 6 7 

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)

Optimizaciones: el código anterior se puede optimizar para buscar x e y en un solo recorrido. Se utilizan dos bucles para mantener el programa simple.

Enfoque más simple:

// C++ program to swap two given nodes
// of a linked list
#include <iostream>
 
using namespace std;
 
// A linked list node class
class Node
{
    public:
    int data;
    class Node* next;
 
    // constructor
    Node(int val, Node* next)
        : data(val)
        , next(next)
    {
    }
 
    // print list from this
    // to last till null
    void printList()
    {
        Node* node = this;
 
        while (node != NULL)
        {
            cout << node->data << " ";
            node = node->next;
        }
 
        cout << endl;
    }
};
 
// Function to add a node
// at the beginning of List
void push(Node** head_ref,
          int new_data)
{
    // Allocate node
    (*head_ref) = new Node(new_data,
                           *head_ref);
}
 
void swap(Node*& a, Node*& b)
{
    Node* temp = a;
    a = b;
    b = temp;
}
 
void swapNodes(Node** head_ref,
               int x, int y)
{
    // Nothing to do if x and
    // y are same
    if (x == y)
        return;
 
    Node **a = NULL, **b = NULL;
 
    // Search for x and y in the linked list
    // and store their pointer in a and b
    while (*head_ref)
    {
        if ((*head_ref)->data == x)
        {
            a = head_ref;
        }
 
        else if ((*head_ref)->data == y)
        {
            b = head_ref;
        }
 
        head_ref = &((*head_ref)->next);
    }
 
    // If we have found both a and b
    // in the linked list swap current
    // pointer and next pointer of these
    if (a && b)
    {
        swap(*a, *b);
        swap(((*a)->next), ((*b)->next));
    }
}
 
// Driver code
int main()
{
    Node* start = NULL;
 
    // The constructed linked list is:
    // 1->2->3->4->5->6->7
    push(&start, 7);
    push(&start, 6);
    push(&start, 5);
    push(&start, 4);
    push(&start, 3);
    push(&start, 2);
    push(&start, 1);
 
    cout << "Linked list before calling swapNodes() ";
    start->printList();
    swapNodes(&start, 6, 1);
    cout << "Linked list after calling swapNodes() ";
    start->printList();
}

Producción:

Linked list before calling swapNodes() 1 2 3 4 5 6 7 
Linked list after calling swapNodes() 6 2 3 4 5 1 7 

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)

Consulte el artículo completo sobre Intercambiar Nodes en una lista vinculada sin intercambiar datos para obtener más detalles.