Étant donné une liste chaînée, échangez les éléments de la liste chaînée par paires

Par exemple, pour résoudre le problème de la nécessité d'échanger des paires de nœuds présents dans une liste chaînée puis de l'imprimer

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

Il existe deux façons d'obtenir une solution avec une complexité temporelle de O(N), où N est la liste chaînée que nous fournissons mesure, nous allons donc maintenant explorer ces deux méthodes

Méthode itérative

Dans cette méthode, nous allons parcourir les éléments de la liste chaînée et les échanger paire par paire jusqu'à ce qu'ils atteignent NULL.

Exemple

#include <bits/stdc++.h>
using namespace std;
class Node { // node of our list
public:
    int data;
    Node* next;
};
void swapPairwise(Node* head){
    Node* temp = head;
    while (temp != NULL && temp->next != NULL) { // for pairwise swap we need to have 2 nodes hence we are checking
        swap(temp->data,
            temp->next->data); // swapping the data
        temp = temp->next->next; // going to the next pair
    }
}
void push(Node** head_ref, int new_data){ // function to push our data in list
    Node* new_node = new Node(); // creating new node
    new_node->data = new_data;
    new_node->next = (*head_ref); // head is pushed inwards
    (*head_ref) = new_node; // our new node becomes our head
}
void printList(Node* node){ // utility function to print the given linked list
    while (node != NULL) {
       cout << node->data << " ";
       node = node->next;
    }
}
int main(){
    Node* head = NULL;
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
    cout << "Linked list before\n";
    printList(head);
    swapPairwise(head);
    cout << "\nLinked list after\n";
    printList(head);
    return 0;
}

Sortie

Linked list before
1 2 3 4 5
Linked list after
2 1 4 3 5

Nous utiliserons la même formule dans la méthode suivante mais nous allons parcourir la récursion.

Méthode récursive

Dans cette méthode, nous implémentons la même logique par récursion.

Exemple

#include <bits/stdc++.h>
using namespace std;
class Node { // node of our list
public:
    int data;
    Node* next;
};
void swapPairwise(struct Node* head){
    if (head != NULL && head->next != NULL) { // same condition as our iterative
        swap(head->data, head->next->data); // swapping data
        swapPairwise(head->next->next); // moving to the next pair
    }
    return; // else return
}
void push(Node** head_ref, int new_data){ // function to push our data in list
    Node* new_node = new Node(); // creating new node
    new_node->data = new_data;
    new_node->next = (*head_ref); // head is pushed inwards
    (*head_ref) = new_node; // our new node becomes our head
}
void printList(Node* node){ // utility function to print the given linked list
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
}
int main(){
    Node* head = NULL;
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
    cout << "Linked list before\n";
    printList(head);
    swapPairwise(head);
    cout << "\nLinked list after\n";
    printList(head);
    return 0;
}

Sortie

Linked list before
1 2 3 4 5
Linked list after
2 1 4 3 5

Explication du code ci-dessus

Dans cette méthode, nous parcourons la liste chaînée par paires. Maintenant, lorsque nous atteignons une paire, nous échangeons leurs données et passons à la paire suivante. C'est ainsi que notre programme se déroule dans les deux méthodes.

Conclusion

Dans ce tutoriel, nous avons résolu l'échange par paires d'éléments d'une liste chaînée donnée en utilisant la récursivité et l'itération. Nous avons également appris le programme C++ pour ce problème et la méthode complète (générique) pour le résoudre. Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. Nous espérons que vous avez trouvé ce tutoriel utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!