ในปัญหานี้ เราได้รับตัวชี้ไปที่ส่วนหัวของรายการที่เชื่อมโยงและจำนวนเต็ม k ในกลุ่มขนาด k เราจำเป็นต้องกลับรายการเชื่อมโยง ตัวอย่างเช่น −
Input : 1 <-> 2 <-> 3 <-> 4 <-> 5 (doubly linked list), k = 3 Output : 3 <-> 2 <-> 1 <-> 5 <-> 4
แนวทางในการหาทางออก
ในปัญหานี้ เราจะสร้างอัลกอริธึมแบบเรียกซ้ำเพื่อแก้ปัญหานี้ ในแนวทางนี้ เราจะใช้การเรียกซ้ำและแก้ปัญหาโดยใช้สิ่งนั้น
ตัวอย่าง
#include <iostream>
using namespace std;
struct Node {
int data;
Node *next, *prev;
};
// push function to push a node into the list
Node* push(Node* head, int data) {
Node* new_node = new Node();
new_node->data = data;
new_node->next = NULL;
Node* TMP = head;
if (head == NULL) {
new_node->prev = NULL;
head = new_node;
return head;
}
while (TMP->next != NULL) { // going to the last node
TMP = TMP->next;
}
TMP->next = new_node;
new_node->prev = TMP;
return head; // return pointer to head
}
// function to print given list
void printDLL(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
Node* revK(Node* head, int k) {
if (!head)
return NULL;
head->prev = NULL;
Node *TMP, *CURRENT = head, *newHead;
int count = 0;
while (CURRENT != NULL && count < k) { // while our count is less than k we simply reverse the nodes.
newHead = CURRENT;
TMP = CURRENT->prev;
CURRENT->prev = CURRENT->next;
CURRENT->next = TMP;
CURRENT = CURRENT->prev;
count++;
}
if (count >= k) {
head->next = revK(CURRENT, k); // now when if the count is greater or equal
//to k we connect first head to next head
}
return newHead;
}
int main() {
Node* head;
for (int i = 1; i <= 5; i++) {
head = push(head, i);
}
cout << "Original List : ";
printDLL(head);
cout << "\nModified List : ";
int k = 3;
head = revK(head, k);
printDLL(head);
}
ผลลัพธ์
Original List : 1 2 3 4 5 Modified List : 3 2 1 5 4
คำอธิบายของโค้ดด้านบน
ในแนวทางนี้ เรากำลังสำรวจรายการและข้ามผ่านจนกว่าจำนวนของเราจะน้อยกว่า k เราโทรแบบเรียกซ้ำและให้ค่านั้นไปที่ head -> ถัดไป (ในที่นี้เราเพียงแค่ย้อนกลับรายการในขณะที่เราดำเนินการ แต่เมื่อถึง k ของเรา เราจำเป็นต้องทำให้ส่วนหัวของเราชี้ไปที่องค์ประกอบ k อื่นของรายการเช่นถ้า รายการคือ 1 2 3 4 5 และ k ของเราคือ 3 ในรายการนี้ เราย้อนกลับองค์ประกอบตรงกลางเป็น 3 2 1 แต่ตอนนี้เราต้องการ 1 ของเราเพื่อชี้ไปที่ 4 เนื่องจากองค์ประกอบนั้นจะถูกย้อนกลับด้วย นั่นคือเหตุผลที่เราใช้ เรียกซ้ำและทำการพิเศษ if คำสั่ง)
บทสรุป
ในบทความนี้ เราแก้ปัญหาในการย้อนกลับรายการที่เชื่อมโยงแบบทวีคูณในกลุ่มของขนาดที่กำหนดโดยใช้การเรียกซ้ำ . นอกจากนี้เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้และแนวทางทั้งหมดที่เราแก้ไข เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์
