Отстранете го решението за елементи на поврзана листа Leetcode


Ниво на тешкотија Лесно
Често прашувано во Adobe Амазон Јаболко Блумберг капитал Еден Facebook Google Мајкрософт
Поврзан список Чиста чување

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

Во овој проблем, ни се дадени поврзани листа со неговите јазли кои имаат цели вредности. Треба да избришеме некои јазли од списокот кои имаат вредност еднаква на вал Проблемот не бара да се реши на место но ќе разговараме за еден таков пристап.

пример

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

Отстранете го решението за елементи на поврзана листа Leetcode

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

Рекурзивно можеме да ја повикаме истата функција за да ја вратиме главата на бараната листа. Ова го постигнуваме со повикување на функцијата на следните наставки на дадената листа со некои услови. Сепак, треба да се справиме со основниот случај кога списокот е празен. Постои само еден посебен случај:

Ако главата на списокот има вредност еднаква на вал (влез), тогаш, треба да ја вратиме функцијата повикана на нејзиниот следен јазол. Ова е направено за да се избегне тековниот јазол да биде додаден на претходните јазли од списокот (бидејќи комплетот на функции е завршен).

Имплементација на Отстрани врски со елементи на линк код решение

Програма 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 = должината на списокот. Секој елемент го посетуваме само еднаш во најлош случај.

Комплексноста на просторот 

О (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 = должина на списокот

Комплексноста на просторот 

О (1), како што имаме само постојан мемориски простор.