ในบทความนี้ เราจัดการกับรายการที่เชื่อมโยงเพียงอย่างเดียว และภารกิจคือการกลับรายการในกลุ่มของ k ตัวอย่างเช่น −
Input: 1->2->3->4->5->6->7->8->NULL, K = 3 Output: 3->2->1->6->5->4->8->7->NULL Input: 1->2->3->4->5->6->7->8->NULL, K = 5 Output: 5->4->3->2->1->8
สำหรับปัญหานี้ วิธีหนึ่งที่นึกถึงคือการต่อท้ายรายการและย้อนกลับรายการเมื่อรายการย่อยของเรามีขนาดถึง k และดำเนินต่อไป
แนวทางในการหาทางออก
ในแนวทางนี้ โดยทั่วไปเราจะสำรวจผ่านรายการและเก็บตัวนับเพื่อนับจำนวนองค์ประกอบในรายการย่อยของเรา เมื่อตัวนับถึงจำนวน k เราจะกลับส่วนนั้น
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
};
Node* reverse(Node* head, int k) {
if (!head)
return NULL;
Node* curr = head;
Node* next = NULL;
Node* prev = NULL;
int count = 0;
while (curr != NULL && count < k) { // we reverse the list till our count is less than k
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
count++;
}
if (next != NULL) // if our link list has not ended we call reverse function again
head->next = reverse(next, k);
return prev;
}
void push(Node** head_ref, int new_data) { // function for pushing data in the list
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void printList(Node* node) { // function to print linked list
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
cout << "\n";
}
int main() {
Node* head = NULL;
int k = 3; // the given k
push(&head, 8);
push(&head, 7);
push(&head, 6);
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
cout << "Original list \n";
printList(head);
head = reverse(head, k); // this function will return us our new head
cout << "New list \n";
printList(head);
return (0);
} ผลลัพธ์
Original list 1 2 3 4 5 6 7 8 New list 3 2 1 6 5 4 8 7
วิธีการข้างต้นมีความซับซ้อนของเวลา O(N) โดยที่ N คือขนาดของรายการที่เรากำหนด และวิธีนี้ใช้ได้กับการเรียกซ้ำ วิธีการนี้สามารถใช้ได้กับข้อจำกัดที่สูงขึ้นเช่นกัน
คำอธิบายของโค้ดด้านบน
เราจะสำรวจผ่านอาร์เรย์ในแนวทางนี้และย้อนกลับไปเรื่อยๆ จนกว่าตัวแปรตัวนับจะน้อยกว่า k เมื่อตัวนับของเราถึงค่าของ k เราจะเรียกฟังก์ชันการย้อนกลับอื่นเพื่อเชื่อมต่อโหนดสุดท้ายของรายการย่อยนี้กับโหนดแรกของรายการย่อยที่ย้อนกลับถัดไป สิ่งนี้ถูกกระทำโดยการเรียกซ้ำ
บทสรุป
ในบทความนี้ เราแก้ปัญหาในการย้อนกลับรายการที่เชื่อมโยงในกลุ่มของขนาดที่กำหนดโดยใช้การเรียกซ้ำ นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ ( Normal) ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์
