Tauschen Sie bei einer gegebenen verknüpften Liste die Elemente in der verknüpften Liste paarweise aus-C++-php.cn

Tauschen Sie bei einer gegebenen verknüpften Liste die Elemente in der verknüpften Liste paarweise aus

WBOY

Freigeben： 2023-08-26 10:33:10

nach vorne

1329 Leute haben es durchsucht

Tauschen Sie bei einer gegebenen verknüpften Liste die Elemente in der verknüpften Liste paarweise aus

Zum Beispiel, um das Problem zu lösen, dass Knotenpaare in einer verknüpften Liste ausgetauscht und dann gedruckt werden müssen

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

Nach dem Login kopieren

Es gibt zwei Möglichkeiten, eine Lösung mit der Zeitkomplexität O(N) zu erreichen, wobei N ist Die Größe der verknüpften Liste wird von uns bereitgestellt. Jetzt werden wir diese beiden Methoden untersuchen.

< h2>Beispiel

#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;
}

Nach dem Login kopieren

Ausgabe

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

Nach dem Login kopieren

Wir werden dieselbe Formel in der folgenden Methode verwenden, aber wir werden durch Rekursion iterieren.

Rekursive Methode

In dieser Methode implementieren wir dieselbe Logik durch Rekursion.

Beispiel

#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;
}

Nach dem Login kopieren

Ausgabe

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

Nach dem Login kopieren

Erklärung des obigen Codes

Bei dieser Methode durchlaufen wir die verknüpfte Liste paarweise. Wenn wir nun ein Paar erreichen, tauschen wir dessen Daten aus und gehen zum nächsten Paar über. So läuft unser Programm bei beiden Methoden ab.

Fazit

In diesem Tutorial haben wir den paarweisen Austausch von Elementen einer bestimmten verknüpften Liste mithilfe von Rekursion und Iteration gelöst. Wir haben auch das C++-Programm für dieses Problem und die vollständige (generische) Methode zu seiner Lösung gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen Sprachen schreiben. Wir hoffen, dass Sie dieses Tutorial hilfreich fanden.

Das obige ist der detaillierte Inhalt vonTauschen Sie bei einer gegebenen verknüpften Liste die Elemente in der verknüpften Liste paarweise aus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!