Уклоните решење за Леетцоде повезаних елемената листе  


Ниво тешкоће Лако
Често питани у адобе амазонка јабука Блоомберг Цапитал Оне фацебоок гоогле мицрософт
алгоритми шифрирање Интервју интервјупреп ЛеетЦоде ЛеетЦодеСолутионс Повезана листа Чисто складиштење

Изјава о проблему  

У овом проблему добијамо повезаност листа са својим чворовима који имају целобројне вредности. Морамо да избришемо неке чворове са листе чији је вредност једнака вал. Проблем није потребан за решавање на месту али ми ћемо разговарати о једном таквом приступу.

Пример

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

Анализа сложености решења комплемента са бројевима

Сложеност времена

НА), где је Н = дужина листе. У најгорем случају сваки елемент посећујемо само једном.

Види такође
Флоод Филл ЛеетЦоде

Сложеност простора 

О (1). Као што код следи рекурзија репа.

Приступ (итеративни)  

Да бисмо избрисали било који чвор, треба да имамо адресу његовог претходног чвора, како бисмо претходну тачку могли усмерити на његов следећи. Ово даје идеју да се одржи а претходна показивач који ће нам помоћи да манипулишемо показивачима на листи. Сада је важно да први чвор на листи нема ниједан претходни чвор. Дакле, треба да додамо сентинел чвор на почетку листе. Сада можемо прелазити кроз први чвор на листи (чвор поред сентинел чвора) и суочили бисмо се са два услова:

1.) ноде-> валуе == вал: У овом случају ћемо поставити прев-> нект = ноде-> нект. Ово ће повезати претходни тренутни чвор са следећим тренутног чвора и избрисати тренутни чвор користећи: делете (цуррентНоде)

2.) Иначе смо само поставили прев = глава за предстојеће чворове.

На крају, следећа од стражара је обавезна листа.

Имплементација решења за уклањање повезаних елемената са Леетцоде решењем

Програм Ц ++

#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), јер ми само константно меморијски простор.