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
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;
}Ausgabe
Linked list before 1 2 3 4 5 Linked list after 2 1 4 3 5
In dieser Methode implementieren wir dieselbe Logik durch Rekursion.
#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;
}Ausgabe
Linked list before 1 2 3 4 5 Linked list after 2 1 4 3 5
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!
