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

C++ में लिंक्ड लिस्ट कंपोनेंट्स


मान लीजिए हमें एक हेड दिया गया है; यह एक लिंक्ड लिस्ट का हेड नोड है जिसमें अद्वितीय पूर्णांक मान हैं। अब हमें सूची G भी दी गई है, जो लिंक्ड लिस्ट में मानों का एक सबसेट है। हमें G में कनेक्टेड कंपोनेंट्स की संख्या ढूंढनी है, जहां दो मान कनेक्टेड हैं यदि वे लिंक्ड लिस्ट में लगातार दिखाई देते हैं। तो यदि सूची [0,1,2,3] जैसी है और G = [0,1,3], तो आउटपुट 2 होगा, क्योंकि 0 और 1 कनेक्टेड हैं, इसलिए दो सूचियां [0,1] और [3] हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

  • ret := 0, एक सेट s बनाएं, और G के सभी तत्वों को s में डालें
  • flag := false
  • जब तक head null नहीं है
    • x := head का मान
    • यदि s में x है, तो
      • यदि flag false है, तो ret को 1 से बढ़ाएं
      • flag := true
    • अन्यथा flag := false सेट करें
    • head := head का अगला
  • ret लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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

class Solution {
public:
    int numComponents(ListNode* head, vector<int>& G) {
        int ret = 0;
        set < int > s;
        for(int i = 0; i < G.size(); i++)s.insert(G[i]);
        bool flag = false;
        while(head){
            int x = head->val;
            if(s.count(x)){
                if(!flag) ret++;
                flag = true;
            }else flag = false;
            head = head->next;
        }
        return ret;
    }
};

main(){
    vector<int> v1 = {0,1,2,3};
    vector<int> v2 = {0,1,3};
    ListNode *h1 = make_list(v1);
    Solution ob;
    cout << (ob.numComponents(h1, v2));
}

इनपुट

[0,1,2,3] [0,1,3]

आउटपुट

2

  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