Để giải quyết một vấn đề trong đó chúng tôi bắt buộc phải hoán đổi các nút theo cặp có trong danh sách được liên kết và sau đó in nó ra, chẳng hạn như
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
Có hai cách để tiếp cận giải pháp cả hai đều có độ phức tạp về thời gian là O (N), trong đó N là kích thước của danh sách liên kết đã cung cấp của chúng tôi, vì vậy bây giờ chúng ta sẽ khám phá cả hai cách tiếp cận
Phương pháp tiếp cận lặp lại
Chúng tôi sẽ lặp qua các phần tử danh sách được liên kết trong cách tiếp cận này và hoán đổi từng cặp cho đến khi chúng đạt đến NULL.
Ví dụ
#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;
} Đầu ra
Linked list before 1 2 3 4 5 Linked list after 2 1 4 3 5
Chúng tôi sẽ sử dụng cùng một công thức trong cách tiếp cận sau đây, nhưng chúng tôi sẽ lặp lại thông qua đệ quy.
Phương pháp tiếp cận đệ quy
Trong cách tiếp cận này, chúng tôi đang triển khai cùng một logic với đệ quy.
Ví dụ
#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;
} Đầu ra
Linked list before 1 2 3 4 5 Linked list after 2 1 4 3 5
Giải thích về Quy tắc trên
Trong cách tiếp cận này, chúng tôi duyệt qua danh sách được liên kết của chúng tôi theo từng cặp. Bây giờ, khi chúng tôi tiếp cận một cặp, chúng tôi trao đổi dữ liệu của chúng và chuyển sang cặp tiếp theo và đó là cách chương trình của chúng tôi tiến hành theo cả hai phương pháp.
Kết luận
Trong hướng dẫn này, chúng tôi giải quyết các phần tử hoán đổi theo cặp của một danh sách được liên kết nhất định bằng cách sử dụng đệ quy và lặp lại. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.