ในการแก้ปัญหาที่เราจำเป็นต้องสลับโหนดแบบคู่ที่มีอยู่ในรายการที่เชื่อมโยงแล้วพิมพ์ออกมา ตัวอย่างเช่น
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
มีสองวิธีในการแก้ปัญหาทั้งสองแบบเพื่อให้มีเวลาที่ซับซ้อนของ O(N) โดยที่ N คือขนาดของรายการลิงก์ที่เราให้ไว้ ดังนั้นตอนนี้เราจะสำรวจทั้งสองวิธี
แนวทางการทำซ้ำ
เราจะทำซ้ำผ่านองค์ประกอบรายการที่เชื่อมโยงในแนวทางนี้ และสลับคู่กันจนกว่าจะถึงค่า NULL
ตัวอย่าง
#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;
} ผลลัพธ์
Linked list before 1 2 3 4 5 Linked list after 2 1 4 3 5
เราจะใช้สูตรเดียวกันในแนวทางต่อไปนี้ แต่เราจะทำซ้ำผ่านการเรียกซ้ำ
แนวทางแบบเรียกซ้ำ
ในแนวทางนี้ เรากำลังใช้ตรรกะเดียวกันกับการเรียกซ้ำ
ตัวอย่าง
#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;
} ผลลัพธ์
Linked list before 1 2 3 4 5 Linked list after 2 1 4 3 5
คำอธิบายของโค้ดด้านบน
ในแนวทางนี้ เราสำรวจผ่านรายการที่เชื่อมโยงเป็นคู่ ตอนนี้ เมื่อเราไปถึงคู่ เราสลับข้อมูลและย้ายไปยังคู่ถัดไป และนั่นคือวิธีที่โปรแกรมของเราดำเนินการในทั้งสองวิธี
บทสรุป
ในบทช่วยสอนนี้ เราจะแก้ไของค์ประกอบการสลับคู่ของรายการที่เชื่อมโยงโดยใช้การเรียกซ้ำและการวนซ้ำ นอกจากนี้เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ (ปกติ) ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์
