लिंक्ड यादी घटकांचे लेटकोड सोल्यूशन काढा


अडचण पातळी सोपे
वारंवार विचारले अडोब ऍमेझॉन सफरचंद ब्लूमबर्ग कॅपिटल वन फेसबुक Google मायक्रोसॉफ्ट
दुवा साधलेली यादी शुद्ध संग्रह

समस्या विधान

या समस्येमध्ये, आम्हाला दुवा दिलेला आहे यादी त्याच्या नोड्ससह पूर्णांक मूल्ये. आम्हाला सूचीमधून काही नोड्स हटविणे आवश्यक आहे ज्याचे मूल्य समान आहे व्हॉल. समस्येचे निराकरण करण्याची आवश्यकता नाही ठिकाणी परंतु आम्ही अशाच एका दृष्टिकोनावर चर्चा करू.

उदाहरण

List = 1 -> 2 -> 2 -> 3 -> 4 , val = 2
1 3 4
List = 2 -> 2 -> 2 -> 2 , val = 2
Empty List

लिंक्ड यादी घटकांचे लेटकोड सोल्यूशन काढा

दृष्टीकोन (रिकर्सीव्ह)

आवश्यक यादीचा प्रमुख परत करण्यासाठी आम्ही वारंवार त्याच कार्यावर कॉल करू शकतो. आम्ही दिलेल्या अटींच्या पुढील प्रत्यय वर फंक्शनला काही अटींसह कॉल करून हे साध्य करतो. तथापि, सूची रिक्त असताना आम्हाला बेस केस हाताळणे आवश्यक आहे. फक्त एकच विशेष प्रकरण आहेः

जर यादीच्या शीर्षकाचे मूल्य समान असेल व्हॉल (इनपुट), नंतर, आपल्याला त्याच्या पुढील नोडवर कॉल केलेले कार्य परत करणे आवश्यक आहे. सध्याच्या नोडला सूचीच्या मागील नोड्समध्ये जोडण्यासाठी टाळण्यासाठी केले जाते (फंक्शन स्टॅक पूर्ण झाल्यावर).

लिंक्ड लिस्ट एलिमेंट्स लीटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#include <bits/stdc++.h>

using namespace std;

struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

void print(listNode* head)
{
    if(head == NULL) {
        cout << "Empty List\n";
        return;
    }
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}

listNode* removeElements(listNode* head, int val) {
    if(head == NULL) {
        return head;
    }
    if(head->value == val) {
        listNode* temp = head->next;
        head->next = NULL;
        delete(head);
        return removeElements(temp , val);
    }

    head->next = removeElements(head->next , val);
    return head;
}

int main() {
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(2);
    head->next->next->next = new listNode(3);
    head->next->next->next->next = new listNode(4);

    int val = 2;
    print(removeElements(head , val));
    return 0;
}

जावा कार्यक्रम

class listNode
{
    int value;
    listNode next;
    listNode(int x)
    {
        value = x;
        next = null;
    }
};

class remove_linked_list_elements {
    public static void print(listNode head) {
        if(head == null) {
            System.out.println("Empty List");
            return;
        }
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        System.out.println();
        return;
    }

    public static listNode removeElements(listNode head, int val) {
        if(head == null) {
            return head;
        }
        if(head.value == val) {
            return removeElements(head.next , val);
        }

        head.next = removeElements(head.next , val);
        return head;
    }

    public static void main(String args[]) {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(2);
        head.next.next.next = new listNode(3);
        head.next.next.next.next = new listNode(4);

        int val = 2;
        print(removeElements(head , val));
    }
}
1 3 4

संख्या पूरक लेटकोड सोल्यूशनचे जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), जेथे N = सूचीची लांबी. आम्ही प्रत्येक घटकास सर्वात वाईट परिस्थितीत एकदाच भेट देतो.

स्पेस कॉम्प्लेक्सिटी 

ओ (1). कोड खालीलप्रमाणे आहे शेपटी पुनरावृत्ती.

दृष्टीकोन (Iterative)

कोणताही नोड हटविण्यासाठी आपल्याकडे मागील नोडचा पत्ता असणे आवश्यक आहे जेणेकरुन आपण मागील बिंदू त्याच्या पुढील भागापर्यंत पोहोचवू शकाल. हे एक राखण्यासाठी एक कल्पना देते मागील सूचीतील पॉईंटर्स हाताळण्यास आम्हाला मदत करणारा पॉईंटर. आता, महत्त्वाचा मुद्दा म्हणजे सूचीतील पहिल्या नोडला मागील नोड नाही. तर, सूचीच्या सुरूवातीस आम्हाला एक सेन्टिनल नोड जोडण्याची आवश्यकता आहे. आता आम्ही यादीतील पहिल्या नोडमधून पुढे जाऊ शकतो (सेन्टिनल नोडच्या पुढे नोड) आणि पुढील दोन अटींचा सामना करावा लागतो.

1.) नोड-> मूल्य == व्हॉल: या प्रकरणात आम्ही सेट करू prev-> next = node-> next. हे सद्य नोडच्या मागील भागास वर्तमान नोडच्या पुढील भागाशी जोडेल आणि हे वापरून नोड हटवेल: हटवा (चालू नोड)

२) अन्यथा, आम्ही फक्त सेट करतो prev = डोके आगामी नोड्ससाठी.

शेवटी, सेन्टिनल पुढील आवश्यक यादी आहे.

लिंक्ड लिस्ट एलिमेंट्स लीटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#include <bits/stdc++.h>

using namespace std;

struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

void print(listNode* head)
{
    if(head == NULL) {
        cout << "Empty List\n";
        return;
    }
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}

listNode* removeElements(listNode* head, int val) {
    listNode *dummy = new listNode(-1) , *prev = dummy , *toDelete;
    dummy->next = head;

    while(head != NULL) {
        if(head->value == val) {
            toDelete = head;
            prev->next = head->next;
            head = head->next;
            toDelete->next = NULL;
        }
        else {
            toDelete = NULL;
            prev = head;
            head = head->next;
        }
        if(toDelete != NULL)
            delete(toDelete);
    }

    return dummy->next;
}

int main() {
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(2);
    head->next->next->next = new listNode(3);
    head->next->next->next->next = new listNode(4);

    int val = 2;
    print(removeElements(head , val));
    return 0;
}

जावा कार्यक्रम

class listNode
{
    int value;
    listNode next;
    listNode(int x)
    {
        value = x;
        next = null;
    }
};

class remove_linked_list_elements {
    public static void print(listNode head) {
        if(head == null) {
            System.out.println("Empty List");
        return;
        }
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        System.out.println();
        return;
    }

    public static listNode removeElements(listNode head, int val) {
        listNode dummy = new listNode(-1) , prev = dummy , toDelete;
        dummy.next = head;

        while(head != null) {
            if(head.value == val) {
                prev.next = head.next;
            }
            else {
                prev = head;
            }
            head = head.next;
        }

        return dummy.next;
    }

    public static void main(String args[]) {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(2);
        head.next.next.next = new listNode(3);
        head.next.next.next.next = new listNode(4);

        int val = 2;
        print(removeElements(head , val));
    }
}
1 3 4

लिंक्ड लिस्ट एलिमेंट्स लीटकोड सोल्यूशनचे जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन)जेव्हा आम्ही संपूर्ण यादी पुनरावृत्ती करतो. एन = सूचीची लांबी

स्पेस कॉम्प्लेक्सिटी 

ओ (1), आम्ही केवळ मेमरी स्पेस म्हणूनच.