লিঙ্কড লিস্ট এলিমেন্টস লেটকোড সলিউশন সরান


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক আপেল ব্লুমবার্গ ক্যাপিটাল ওয়ান ফেসবুক গুগল মাইক্রোসফট
যোজিত তালিকা বিশুদ্ধ সংগ্রহস্থল

সমস্যা বিবৃতি

এই সমস্যায়, আমাদের একটি লিঙ্কযুক্ত দেওয়া হয় তালিকা এর নোডগুলির সাথে পূর্ণসংখ্যার মান রয়েছে। আমাদের তালিকা থেকে কিছু নোড মুছতে হবে যার সমান মান রয়েছে Val। সমস্যাটির সমাধান করার প্রয়োজন নেই জায়গায় তবে আমরা এই জাতীয় একটি পদ্ধতি নিয়ে আলোচনা করব।

উদাহরণ

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 = তালিকার দৈর্ঘ্য। আমরা প্রতিটি উপাদানটি সবচেয়ে খারাপ ক্ষেত্রে একবারে পরিদর্শন করি।

স্পেস জটিলতা ity 

ও (1)। কোড অনুসরণ হিসাবে লেজ পুনরাবৃত্তি.

পন্থা (Iterative)

যে কোনও নোড মোছার জন্য, আমাদের আগের নোডের ঠিকানা থাকা দরকার, যাতে আমরা পূর্বের পয়েন্টটি এর পরবর্তী অংশে তৈরি করতে পারি। এটি একটি বজায় রাখতে একটি ধারণা দেয় আগে পয়েন্টার যা আমাদের তালিকায় পয়েন্টারগুলি পরিচালনা করতে সহায়তা করবে। এখন, গুরুত্বপূর্ণ বিষয়টি হল তালিকার প্রথম নোডের কোনও পূর্ববর্তী নোড নেই। সুতরাং, তালিকার শুরুতে আমাদের একটি সেন্ডিনেল নোড যুক্ত করা দরকার। এখন, আমরা তালিকার প্রথম নোডটি পেরিয়ে যেতে পারি (সেন্ডিনেল নোডের পাশের নোড) এবং নিম্নলিখিত দুটি শর্তের মুখোমুখি হতে পারি:

1.) নোড-> মান == ভাল: এই ক্ষেত্রে, আমরা সেট করব prev-> পরের = নোড-> পরবর্তী। এটি বর্তমান নোডের পূর্ববর্তীটি বর্তমান নোডের পরবর্তীটির সাথে সংযুক্ত করবে এবং এটি ব্যবহার করে বর্তমান নোডটি মুছে ফেলবে: মুছুন (বর্তমান নোড)

2.) অন্যথায়, আমরা ঠিক সেট 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

লিঙ্কড লিস্ট এলিমেন্টগুলি সরান সম্পর্কিত জটিলতা বিশ্লেষণ লেটকোড সমাধান

সময় জটিলতা

চালু), যেমন আমরা একবারে পুরো তালিকাটি পুনরাবৃত্তি করি। N = তালিকার দৈর্ঘ্য

স্পেস জটিলতা ity 

ও (1)যেমন আমরা কেবল স্থির মেমরির জায়গা