Dada una lista enlazada individualmente, escriba una función para intercambiar elementos por pares. Por ejemplo, si la lista enlazada es 1->2->3->4->5->6->7 entonces la función debería cambiarla a 2->1->4->3->6->5 ->7, y si la lista enlazada es 1->2->3->4->5->6 entonces la función debería cambiarla a 2->1->4->3->6->5
Este problema ha sido discutido aquí . La solución proporcionada allí intercambia datos de Nodes. Si los datos contienen muchos campos, habrá muchas operaciones de intercambio. Así que cambiar enlaces es una mejor idea en general. La siguiente es la implementación que cambia los enlaces en lugar de intercambiar datos.
C
/* This program swaps the nodes of
linked list rather than swapping
the field from the nodes. Imagine
a case where a node contains many
fields, there will be plenty of
unnecessary swap calls. */
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
// A linked list node
struct Node
{
int data;
struct Node* next;
};
/* Function to pairwise swap
elements of a linked list */
void pairWiseSwap(struct Node** head)
{
// If linked list is empty or there
// is only one node in list
if (*head == NULL ||
(*head)->next == NULL)
return;
// Initialize previous and current
// pointers
struct Node* prev = *head;
struct Node* curr = (*head)->next;
// Change head before proceeding
*head = curr;
// Traverse the list
while (true)
{
struct Node* next = curr->next;
// Change next of current as
// previous node
curr->next = prev;
// If next NULL or next is the
// last node
if (next == NULL ||
next->next == NULL)
{
prev->next = next;
break;
}
// Change next of previous to
// next next
prev->next = next->next;
// Update previous and curr
prev = next;
curr = prev->next;
}
}
/* Function to add a node at the
beginning of Linked 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 pairWiseSwap() ");
printList(start);
pairWiseSwap(&start);
printf("
Linked list after calling pairWiseSwap() ");
printList(start);
getchar();
return 0;
}
Producción:
Linked list before calling pairWiseSwap() 1 2 3 4 5 6 7 Linked list after calling pairWiseSwap() 2 1 4 3 6 5 7
Complejidad de tiempo: La complejidad de tiempo del programa anterior es O(n) donde n es el número de Nodes en una lista enlazada dada. El bucle while realiza un recorrido de la lista enlazada dada.
Espacio Auxiliar: O(1)
A continuación se muestra la implementación recursiva del mismo enfoque. Cambiamos los dos primeros Nodes y recurrimos para la lista restante. Gracias a geek y omer salem por sugerir este método.
C
/* This program swaps the nodes of linked list
rather than swapping the field from the nodes.
Imagine a case where a node contains many
fields, there will be plenty of unnecessary
swap calls. */
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
// A linked list node
struct node
{
int data;
struct node* next;
};
/* Function to pairwise swap elements of
a linked list. It returns head of the
modified list, so return value of this
node must be assigned */
struct node* pairWiseSwap(struct node* head)
{
// Base Case: The list is empty or has
// only one node
if (head == NULL ||
head->next == NULL)
return head;
// Store head of list after two nodes
struct node* remaining =
head->next->next;
// Change head
struct node* newhead = head->next;
// Change next of second node
head->next->next = head;
// Recur for remaining list and change
// next of head
head->next = pairWiseSwap(remaining);
// Return new head of modified list
return newhead;
}
/* Function to add a node at the
beginning of Linked 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 pairWiseSwap() ");
printList(start);
// NOTE THIS CHANGE
start = pairWiseSwap(start);
printf("
Linked list after calling pairWiseSwap() ");
printList(start);
return 0;
}
Producción:
Linked list before calling pairWiseSwap() 1 2 3 4 5 6 7 Linked list after calling pairWiseSwap() 2 1 4 3 6 5 7
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)
¡ Consulte el artículo completo sobre los elementos de intercambio por pares de una lista vinculada determinada cambiando los enlaces 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