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.
- xey pueden o no ser adyacentes.
- Cualquiera de los dos, x o y, puede ser un Node principal.
- O x o y puede ser el último Node.
- 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
// C program to swap the nodes of linked list
// rather than swapping the field from the nodes.
#include <stdio.h>
#include <stdlib.h>
// A linked list node
struct Node
{
int data;
struct Node* next;
};
/* Function to swap nodes x and y in linked list
by changing links */
void swapNodes(struct 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
struct 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
struct 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
struct Node* temp = currY->next;
currY->next = currX->next;
currX->next = temp;
}
// Function to add a node at the
// beginning of List
void push(struct Node** head_ref,
int new_data)
{
// Allocate node
struct Node* new_node =
(struct Node*)malloc(sizeof(struct 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(struct Node* node)
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
// Driver code
int main()
{
struct 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);
printf("Linked list before calling swapNodes() ");
printList(start);
swapNodes(&start, 4, 3);
printf("Linked list after calling swapNodes() ");
printList(start);
return 0;
}
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)
Consulte el artículo completo sobre Intercambiar Nodes en una lista vinculada sin intercambiar datos 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