લિંક્ડ સૂચિ તત્વો લીટકોડ સોલ્યુશનને દૂર કરો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન સફરજન બ્લૂમબર્ગ કેપિટલ વન ફેસબુક Google માઈક્રોસોફ્ટ
લિંક્ડ-સૂચિ શુદ્ધ સંગ્રહ

સમસ્યા નિવેદન

આ સમસ્યામાં, અમને એક લિંક્ડ આપવામાં આવે છે યાદી તેના ગાંઠો સાથે પૂર્ણાંક મૂલ્યો છે. આપણે સૂચિમાંથી કેટલાક ગાંઠો કા deleteી નાખવાની જરૂર છે જેની કિંમત સમાન છે વ valલ. સમસ્યા હલ કરવાની જરૂર નથી જગ્યા માં પરંતુ અમે આવા એક અભિગમ પર ચર્ચા કરીશું.

ઉદાહરણ

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

લિંક્ડ સૂચિ તત્વો લીટકોડ સોલ્યુશનને દૂર કરો

અભિગમ (પુનરાવર્તિત)

આવશ્યક સૂચિના વડાને પરત કરવા માટે આપણે વારંવાર સમાન કાર્યને ક callલ કરી શકીએ છીએ. અમે કેટલીક શરતો સાથે આપેલ સૂચિના અનુગામી પ્રત્યયો પર ફંક્શનને બોલાવીને આ પ્રાપ્ત કરીએ છીએ. જો કે, સૂચિ ખાલી હોય ત્યારે આપણે બેઝ કેસને હેન્ડલ કરવાની જરૂર છે. ફક્ત એક જ ખાસ કેસ છે:

જો સૂચિના વડાનું મૂલ્ય બરાબર છે વાલ (ઇનપુટ), તે પછી, આપણે તેના આગલા નોડ પર ક calledલ કરેલા ફંક્શનને પાછા આપવાની જરૂર છે. સૂચિના પહેલાના ગાંઠોમાં જોડાયેલા વર્તમાન નોડને ટાળવા માટે આ કરવામાં આવે છે (કારણ કે ફંક્શન સ્ટેક પૂર્ણ થયું છે).

લિંક્ડ લિસ્ટ એલિમેન્ટ્સ લીટકોડ સોલ્યુશન દૂર કરોની અમલીકરણ

સી ++ પ્રોગ્રામ

#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

સંખ્યાના પૂરક લેટકોડ સોલ્યુશનનું જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), જ્યાં એન = સૂચિની લંબાઈ. અમે દરેક ઘટકની ખરાબ પરિસ્થિતિમાં માત્ર એક જ વાર મુલાકાત લઈએ છીએ.

અવકાશ જટિલતા 

ઓ (1). કોડ નીચે મુજબ છે પૂંછડી રિકર્ઝન.

અભિગમ (Iterative)

કોઈપણ નોડને કા deleteી નાખવા માટે, આપણી પાસે તેના પાછલા નોડનું સરનામું હોવું જરૂરી છે, જેથી આપણે પાછલા મુદ્દાને તેના આગળના ભાગમાં બનાવી શકીએ. આ એક જાળવવા માટે એક વિચાર આપે છે અગાઉના પોઇન્ટર કે જે અમને સૂચિમાંના પોઇંટરની ચાલાકી કરવામાં મદદ કરશે. હવે, મહત્વનો મુદ્દો એ છે કે સૂચિમાં પ્રથમ નોડમાં અગાઉના નોડ નથી. તેથી, સૂચિની શરૂઆતમાં અમને સેંટિનેલ નોડ ઉમેરવાની જરૂર છે. હવે, આપણે સૂચિમાં પ્રથમ નોડ (સેન્ટિનેલ નોડની બાજુમાં નોડ) પસાર કરી શકીએ છીએ અને નીચેની બે શરતોનો સામનો કરવો પડશે:

1.) નોડ-> મૂલ્ય == વ :લ: આ કિસ્સામાં, અમે સેટ કરીશું prev-> next = નોડ-> આગળ. આ વર્તમાન નોડના પાછલા ભાગને વર્તમાન નોડની આગળની સાથે જોડશે, અને વર્તમાન નોડનો ઉપયોગ કરીને કા deleteી નાખશે: કા currentી નાખો (ચાલુ નોડ)

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

લિંક્ડ લિસ્ટ એલિમેન્ટ્સ લીટકોડ સોલ્યુશનનું જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), જેમ આપણે એકવાર આખી સૂચિને ફરી વળવું. એન = સૂચિની લંબાઈ

અવકાશ જટિલતા 

ઓ (1), કારણ કે આપણે ફક્ત સતત મેમરી સ્પેસ કરીએ છીએ.