אַראָפּנעמען לינקעד רשימה עלעמענץ לעעטקאָדע סאַלושאַן


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַדאָובי אַמאַזאָן עפּל בלומבערג Capital One facebook גוגל מייקראָסאָפֿט
לינקעד-רשימה ריין סטאָרידזש

פּראָבלעם סטאַטעמענט

אין דעם פּראָבלעם, מיר געבן אַ לינק רעשימע מיט די נאָודז מיט גאַנץ וואַלועס. מיר דאַרפֿן צו ויסמעקן עטלעכע נאָודז פֿון דער רשימה וואָס זענען ווערט גלייַך צו val. די פּראָבלעם דאַרף נישט זיין סאַלווד אין פּלאַץ אָבער מיר וועלן דיסקוטירן איין אַזאַ צוגאַנג.

בייַשפּיל

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

אַראָפּנעמען לינקעד רשימה עלעמענץ לעעטקאָדע סאַלושאַן

צוגאַנג (רעקורסיווע)

מיר קענען רעקורסיוועלי רופן די זעלבע פונקציע צו צוריקקומען די הויפּט פון די פארלאנגט רשימה. מיר דערגרייכן דאָס דורך רופן די פונקציע אויף סאַבסאַקוואַנט סאַפיקס פון די געגעבן רשימה מיט עטלעכע באדינגונגען. אָבער, מיר דאַרפֿן צו האַנדלען מיט די באַזע פאַל ווען די רשימה איז ליידיק. עס איז בלויז איין ספּעציעלע פאַל:

אויב דער ראָש פון דער רשימה האט אַ ווערט גלייַך צו וואַל (ינפּוט), דערנאָך, מיר דאַרפֿן צו צוריקקומען די פֿונקציע גערופֿן אויף די ווייַטער נאָדע. דאָס איז דורכגעקאָכט צו ויסמיידן דעם קראַנט נאָדע צו זיין בייגעלייגט צו די פריערדיקע נאָודז פון דער רשימה (ווי די פונקציע סטאַק איז געענדיקט).

ימפּלאַמענטיישאַן פון נעם לינקעד רשימה עלעמענץ לעעטקאָדע סאַלושאַן

C ++ פּראָגראַם

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

Java פּראָגראַם

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), וווּ N = לענג פון דער רשימה. אין ערגסט פאַל מיר באַזוכן יעדער עלעמענט נאָר אַמאָל.

ספעיס קאַמפּלעקסיטי 

אָ (1). ווי דער קאָד גייט עק רעקורסיאָן.

צוגאַנג (יטעראַטיווע)

כּדי צו ויסמעקן קיין נאָדע, מיר דאַרפֿן צו האָבן די אַדרעס פון די פֿריִערדיקע נאָדע, אַזוי אַז מיר קענען מאַכן דעם פריערדיקן פונט צו זיין ווייַטער. דעם גיט אַ געדאַנק צו טייַנען אַ פרייַערדיק טייַטל וואָס וועט העלפֿן אונדז צו מאַניפּולירן פּוינטערז אין דער רשימה. איצט, דער וויכטיק פונט איז אַז דער ערשטער נאָדע אין דער רשימה האט קיין פריערדיקן נאָדע. אין דעם אָנהייב פון דער רשימה, מיר דאַרפֿן צו לייגן אַ סענטינעל נאָדע. איצט מיר קענען דורכגיין דורך דער ערשטער נאָדע אין דער רשימה (נאָדע נאָענט צו די סענטינעל נאָדע) און מיר האָבן צוויי טנאָים:

1.) נאָדע-> ווערט == וואַל: אין דעם פאַל, מיר וועלן שטעלן פּריוו-> ווייַטער = נאָדע-> ווייַטער. דעם וועט פאַרבינדן די פריערדיקע פון ​​די קראַנט נאָדע מיט די ווייַטער פון די קראַנט נאָדע און ויסמעקן די קראַנט נאָדע מיט: ויסמעקן (קראַנט נאָדע)

2.) אַנדערש מיר נאָר שטעלן פּריוו = קאָפּ פֿאַר אַפּקאַמינג נאָודז.

אין די סוף, דער ווייַטער סענטינעל איז די פארלאנגט רשימה.

ימפּלאַמענטיישאַן פון נעם לינקעד רשימה עלעמענץ לעעטקאָדע סאַלושאַן

C ++ פּראָגראַם

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

Java פּראָגראַם

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), ווי מיר יטעראַטע די גאנצע רשימה אַמאָל. N = לענג פון דער רשימה

ספעיס קאַמפּלעקסיטי 

אָ (1), ווי מיר נאָר קעסיידערדיק זיקאָרן פּלאַץ.