Programa C para elementos de intercambio por pares de una lista enlazada dada

Dada una lista enlazada individualmente, escriba una función para intercambiar elementos por pares.

Input: 1->2->3->4->5->6->NULL 
Output: 2->1->4->3->6->5->NULL

Input: 1->2->3->4->5->NULL 
Output: 2->1->4->3->5->NULL

Input: 1->NULL 
Output: 1->NULL

Por ejemplo, si la lista enlazada es 1->2->3->4->5 entonces la función debería cambiarla a 2->1->4->3->5, y si la lista enlazada es entonces el la función debería cambiarlo a.

MÉTODO 1 (Iterativo): 
Comience desde el Node principal y recorra la lista. Al atravesar los datos de intercambio de cada Node con los datos de su siguiente Node. 
A continuación se muestra la implementación del enfoque anterior:

/* C program to pairwise swap elements 
   in a given linked list */
#include <stdio.h>
#include <stdlib.h>
  
// A linked list node 
struct Node 
{
    int data;
    struct Node* next;
};
  
/* Function to swap two integers 
   at addresses a and b */
void swap(int* a, int* b);
  
/* Function to pairwise swap elements 
   of a linked list */
void pairWiseSwap(struct Node* head)
{
    struct Node* temp = head;
  
    /* Traverse further only if there 
       are at-least two nodes left */
    while (temp != NULL && 
           temp->next != NULL) 
    {
        /* Swap data of node with its 
           next node's data */
        swap(&temp->data, 
             &temp->next->data);
  
        // Move temp by 2 for the 
        // next pair 
        temp = temp->next->next;
    }
}
  
// UTILITY FUNCTIONS 
// Function to swap two integers 
void swap(int* a, int* b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
  
/* 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 */
    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);
  
    return 0;
}

Producción:

Linked list before calling pairWiseSwap()
1 2 3 4 5 
Linked list after calling pairWiseSwap()
2 1 4 3 5 

Complejidad temporal: O(n)

MÉTODO 2 (recursivo): 
si hay 2 o más de 2 Nodes en la lista enlazada, intercambie los dos primeros Nodes y llame recursivamente al resto de la lista.
La imagen de abajo es una ejecución en seco del enfoque anterior:

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

/* Recursive function to pairwise swap 
   elements of a linked list */
void pairWiseSwap(struct node* head)
{
    /* There must be at-least two nodes 
       in the list */
    if (head != NULL && head->next != NULL) 
    {
        /* Swap the node's data with data 
           of next node */
        swap(head->data, head->next->data);
  
        /* Call pairWiseSwap() for rest of 
           the list */
        pairWiseSwap(head->next->next);
    }
}

Complejidad de tiempo: O(n)
La solución provista allí intercambia datos de Nodes. Si los datos contienen muchos campos, habrá muchas operaciones de intercambio. Vea esto para una implementación que cambia enlaces en lugar de intercambiar datos.

¡ Consulte el artículo completo sobre los elementos de intercambio por pares de una lista vinculada dada para obtener más detalles!