C में लिंक्ड लिस्ट को रिवर्स करने का प्रोग्राम

इस समस्या में, हमें एक लिंक्ड लिस्ट दी गई है। हमारा कार्य लिंक्ड लिस्ट को रिवर्स करने के लिए एक प्रोग्राम बनाना है।

यह प्रोग्राम दी गई लिंक्ड लिस्ट को रिवर्स करेगा और रिवर्स की गई लिंक्ड लिस्ट लौटाएगा।

लिंक्ड लिस्ट लिंक्स का एक क्रम है जिसमें आइटम होते हैं। प्रत्येक लिंक में दूसरे लिंक से जुड़ने का कनेक्शन होता है।

उदाहरण

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 
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 
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