Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में लिंक्ड लिस्ट का भाग उलटना (Reverse Linked List II)


मान लीजिए हमारे पास एक लिंक्ड लिस्ट है। हमें स्थिति m से n तक के नोड्स को उलटना है। हमें इसे एक ही पास (one pass) में करना है। यदि लिस्ट [1,2,3,4,5] है और m = 2, n = 4, तो परिणाम [1,4,3,2,5] होगा।

आइए चरण देखें:

  • दो विधियां होंगी: reverseN() और reverseBetween()। reverseBetween() मुख्य विधि के रूप में काम करेगी।
  • एक लिंक नोड पॉइंटर successor को null के रूप में परिभाषित करें
  • reverseN निम्नानुसार काम करेगा:
    • यदि n = 1, तो successor := head का next, और head वापस करें
    • last = reverseN(head का next, n - 1)
    • head के next का next = head, और head का next := successor, last वापस करें
  • reverseBetween() विधि इस प्रकार होगी:
    • यदि m = 1, तो reverseN(head, n) वापस करें
    • head का next := reverseBetween(head का next, m – 1, n – 1)

उदाहरण

#include <bits/stdc++.h>
using namespace std;

class ListNode{
public:
    int val;
    ListNode *next;
    ListNode(int data){
        val = data;
        next = NULL;
    }
};

ListNode *make_list(vector<int> v){
    ListNode *head = new ListNode(v[0]);
    for(int i = 1; i < v.size(); i++){
        ListNode *ptr = head;
        while(ptr->next != NULL){
            ptr = ptr->next;
        }
        ptr->next = new ListNode(v[i]);
    }
    return head;
}

void print_list(ListNode *head){
    ListNode *ptr = head;
    cout << "[";
    while(ptr){
        cout << ptr->val << ", ";
        ptr = ptr->next;
    }
    cout << "]" << endl;
}

class Solution {
public:
    ListNode* successor = NULL;
    ListNode* reverseN(ListNode* head, int n){
        if(n == 1){
            successor = head->next;
            return head;
        }
        ListNode* last = reverseN(head->next, n - 1);
        head->next->next = head;
        head->next = successor;
        return last;
    }
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(m == 1){
            return reverseN(head, n);
        }
        head->next = reverseBetween(head->next, m - 1, n - 1);
        return head;
    }
};

int main(){
    Solution ob;
    vector<int> v = {1,2,3,4,5,6,7,8};
    ListNode *head = make_list(v);
    print_list(ob.reverseBetween(head, 2, 6));
}

इनपुट

[1,2,3,4,5,6,7,8] 2 6

आउटपुट

[1, 6, 5, 4, 3, 2, 7, 8, ]
  1. - C++ में क्रमबद्ध लिंक्ड लिस्ट में मेडियन खोजना

    समस्या विवरण इस समस्या में, हमें N तत्वों वाली एक क्रमबद्ध लिंक्ड लिस्ट दी गई है। हमारा कार्य क्रमबद्ध लिंक्ड लिस्ट में मेडियन खोजना है। क्रमबद्ध लिंक्ड लिस्ट एक साधारण लिंक्ड लिस्ट है जिसमें सभी तत्व एक विशिष्ट क्रम में क्रमबद्ध होते हैं। उदाहरण: 4 → 6 → 7 → 9 → NULL मेडियन लिंक्ड लिस्ट का मध्य त

  1. C++ में लिंक्ड सूची को समतल करना C++ में लिंक्ड सूची को समतल करना

    इस समस्या में, हमें दो पॉइंटर नोड्स, राइट और डाउन से युक्त एक लिंक्ड सूची दी गई है। राइट नोड मुख्य लिंक्ड सूची पॉइंटर है। डाउन नोड उस नोड से शुरू होने वाली द्वितीयक लिंक्ड सूची के लिए है। सभी लिंक्ड सूचियाँ सॉर्टेड हैं। हमारा कार्य एक प्रोग्राम बनाना है जो लिंक्ड सूची को समतल करे और परिणामी सूची स

  1. C++ में लिंक्ड सूची के वैकल्पिक नोड्स का योग C++ में लिंक्ड सूची के वैकल्पिक नोड्स का योग

    इस समस्या में, हमें एक लिंक्ड सूची दी गई है। हमारा कार्य लिंक्ड सूची के वैकल्पिक नोड्स का योग प्रिंट करना है। लिंक्ड सूची डेटा संरचनाओं का एक क्रम है जो लिंक्स के माध्यम से एक साथ जुड़े हुए हैं। अब, आइए समस्या पर वापस आते हैं। यहां, हम लिंक्ड सूची के वैकल्पिक नोड्स को जोड़ेंगे। इसका मतलब है हम