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

C++ में लिंक्ड लिस्ट साइकिल II (Linked List Cycle II)


मान लीजिए हमारे पास एक लिंक्ड लिस्ट है, और हमें जांचना है कि इसमें कोई साइकिल (चक्र) है या नहीं। दी गई लिंक्ड लिस्ट में साइकिल को दर्शाने के लिए, हम एक पूर्णांक पॉइंटर pos का उपयोग करेंगे। यह pos लिंक्ड लिस्ट में एक स्थिति दर्शाता है जहां टेल (tail) जुड़ा हुआ है। यदि pos -1 है, तो लिंक्ड लिस्ट में कोई साइकिल नहीं है। उदाहरण के लिए, लिंक्ड लिस्ट [5, 3, 2, 0, -4, 7] है, और pos = 1। तो एक साइकिल मौजूद है, और टेल दूसरे नोड से जुड़ा है। शर्त यह है कि हम लिस्ट को संशोधित नहीं कर सकते।

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

  • slow := head और fast := head
  • जब तक slow, fast और fast का next उपलब्ध है:
    • slow := slow का next
    • fast := fast के next का next
    • यदि slow = fast, तो ब्रेक करें
  • यदि fast खाली नहीं है या fast का next खाली नहीं है, तो null वापस करें
  • यदि slow = fast, तो:
    • slow := head
    • जब तक slow, fast के समान नहीं है:
      • slow := slow का next और fast := fast का next
  • slow वापस करें

उदाहरण

#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;
}

ListNode *get_node(ListNode *head, int pos){
    ListNode *ptr = head;
    if(pos != -1){
        int p = 0;
        while(p < pos){
            ptr = ptr->next;
            p++;
        }
        return ptr;
    }
    return NULL;
}

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(slow && fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) break;
        }
        if(!fast || !fast->next) return NULL;
        if(slow == fast){
            slow = head;
            while(slow != fast){
                slow = slow->next;
                fast = fast->next;
            }
        }
        return slow;
    }
};

int main(){
    Solution ob;
    vector<int> v = {5,3,2,0,-4,7};
    ListNode *head = make_list(v);
    int pos = 1;
    ListNode *lastNode = get_node(head, v.size() - 1);
    lastNode->next = get_node(head, pos);
    cout << "टेल इस नोड से जुड़ा है जिसका मान: " << ob.detectCycle(head)->val;
}

इनपुट

[5,3,2,0,-4,7] 1

आउटपुट

टेल इस नोड से जुड़ा है जिसका मान: 3
  1. 2D मैट्रिक्स से लिंक्ड लिस्ट बनाएं C++ में (पुनरावर्ती दृष्टिकोण) 2D मैट्रिक्स से लिंक्ड लिस्ट बनाएं C++ में (पुनरावर्ती दृष्टिकोण)

    मान लीजिए हमारे पास एक मैट्रिक्स है, हमें इसे पुनरावर्ती दृष्टिकोण का उपयोग करके 2D लिंक्ड लिस्ट में बदलना है। इस लिस्ट में राइट (दायां) और डाउन (नीचे) पॉइंटर होंगे। उदाहरण के लिए, यदि इनपुट इस तरह का है: 10 20 30 40 50 60 70 80 90 तो आउटपुट होगा: इसे हल करने के लिए, हम निम्न चरणों का पाल

  1. C++ में सर्कुलर लिंक्ड लिस्ट में नोड्स की गिनती करें C++ में सर्कुलर लिंक्ड लिस्ट में नोड्स की गिनती करें

    हमें नोड्स के साथ एक सर्कुलर लिंक्ड लिस्ट दी गई है और कार्य सर्कुलर लिंक्ड लिस्ट में मौजूद नोड्स की संख्या की गणना करना है। सर्कुलर लिंक्ड लिस्ट लिंक्ड लिस्ट का एक प्रकार है जिसमें पहला तत्व अंतिम तत्व की ओर इंगित करता है और अंतिम तत्व पहले तत्व की ओर इंगित करता है। सिंगली लिंक्ड लिस्ट और डबली लिं

  1. C++ में बाइनरी ट्री में लिंक्ड लिस्ट C++ में बाइनरी ट्री में लिंक्ड लिस्ट

    मान लीजिए हमारे पास एक बाइनरी ट्री रूट और एक लिंक्ड लिस्ट है जिसका हेड पहला नोड है। हमें True लौटाना है अगर लिंक्ड लिस्ट में हेड से शुरू होने वाले सभी एलिमेंट्स बाइनरी ट्री में किसी डाउनवर्ड पथ से मेल खाते हैं, अन्यथा False। उदाहरण के लिए, अगर ट्री है: और लिंक्ड लिस्ट [1,4,2,6] है, तो आउटपुट true