এই সমস্যাতে, আমাদের একটি লিঙ্কড লিস্ট দেওয়া আছে। আমাদের কাজ হল লিঙ্কড লিস্টটি উল্টে দেওয়ার জন্য একটি প্রোগ্রাম তৈরি করা।
প্রোগ্রামটি দেওয়া লিঙ্কড লিস্টটি উল্টিয়ে উল্টানো লিঙ্কড লিস্টটি রিটার্ন করবে।
লিঙ্কড লিস্ট হল লিংকগুলির একটি ক্রম যাতে আইটেম থাকে। প্রতিটি লিংক অন্য একটি লিংকের সাথে সংযোগ রক্ষা করে।
উদাহরণ
9 → 32 → 65 → 10 → 85 → NULL
উল্টানো লিঙ্কড লিস্ট হল একটি লিঙ্কড লিস্ট যা লিস্টের লিংকগুলি উল্টিয়ে তৈরি করা হয়। লিঙ্কড লিস্টের হেড নোড উল্টানো লিস্টের শেষ নোড হয়ে যায় এবং শেষ নোডটি হেড নোড হয়ে যায়।
উদাহরণ
উপরোক্ত লিঙ্কড লিস্ট থেকে তৈরি উল্টানো লিঙ্কড লিস্ট −
85 → 10 → 65 → 32 → 9 → NULL
দেওয়া লিঙ্কড লিস্টটি উল্টানোর জন্য আমরা প্রক্রিয়ায় তিনটি অতিরিক্ত পয়েন্টার ব্যবহার করব। পয়েন্টারগুলো হবে: previous, after, current।
আমরা previous এবং after কে NULL দিয়ে আরম্ভ করব এবং current কে লিঙ্কড লিস্টের হেড দিয়ে।
এরপর, আমরা প্রাথমিক (অনবর্টিত লিঙ্কড লিস্ট) এর NULL পর্যন্ত পৌঁছালে পর্যন্ত পুনরাবৃত্তি করব এবং নিম্নলিখিত কাজগুলো করব −
after = current → next current → next = previous previous = current current = after
এখন লিঙ্কড লিস্ট উল্টানোর জন্য একটি প্রোগ্রাম তৈরি করি। প্রোগ্রাম তৈরি করার দুটি উপায় থাকতে পারে: একটি ইটেরেটিভ (পুনরাবৃত্তিমূলক) এবং অন্যটি রিকারসিভ (আবৃত্তিমূলক)।
লিঙ্কড লিস্ট উল্টানোর প্রোগ্রাম (টেইল-রিকারসিভ পদ্ধতি)
উদাহরণ
#include <stdio.h>
struct Node {
int data;
struct Node* next;
};
Node* insertNode(int key) {
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
void tailRecRevese(Node* current, Node* previous, Node** head){
if (!current->next) {
*head = current;
current->next = previous;
return;
}
Node* next = current->next;
current->next = previous;
tailRecRevese(next, current, head);
}
void tailRecReveseLL(Node** head){
if (!head)
return;
tailRecRevese(*head, NULL, head);
}
void printLinkedList(Node* head){
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
int main(){
Node* head1 = insertNode(9);
head1->next = insertNode(32);
head1->next->next = insertNode(65);
head1->next->next->next = insertNode(10);
head1->next->next->next->next = insertNode(85);
printf("Linked list : \t");
printLinkedList(head1);
tailRecReveseLL(&head1);
printf("Reversed linked list : \t");
printLinkedList(head1);
return 0;
}
আউটপুট
Linked list : 9 32 65 10 85 Reversed linked list : 85 10 65 32 9
লিঙ্কড লিস্ট উল্টানোর প্রোগ্রাম (ইটেরেটিভ পদ্ধতি)
উদাহরণ
#include <stdio.h>
struct Node {
int data;
struct Node* next;
Node(int data){
this->data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList(){
head = NULL;
}
void interReverseLL(){
Node* current = head;
Node *prev = NULL, *after = NULL;
while (current != NULL) {
after = current->next;
current->next = prev;
prev = current;
current = after;
}
head = prev;
}
void print() {
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
void push(int data){
Node* temp = new Node(data);
temp->next = head;
head = temp;
}
};
int main() {
LinkedList linkedlist;
linkedlist.push(85);
linkedlist.push(10);
linkedlist.push(65);
linkedlist.push(32);
linkedlist.push(9);
printf("Linked List : \t");
linkedlist.print();
linkedlist.interReverseLL();
printf("Reverse Linked List : \t");
linkedlist.print();
return 0;
}
আউটপুট
Linked List : 9 32 65 10 85 Reverse Linked List : 85 10 65 32 9
