Премахнете решението на Leetcode за свързани елементи от списъка


Ниво на трудност Лесно
Често задавани в Кирпич Амазонка ябълка Bloomberg Capital One Facebook Google Microsoft
Свързан списък Чисто съхранение

Декларация за проблема

В този проблем ни е даден свързан списък със своите възли, имащи целочислени стойности. Трябва да изтрием някои възли от списъка, чиято стойност е равна на Вал. Проблемът не изисква да бъде решен на място но ще обсъдим един такъв подход.

Пример

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

Премахнете решението на Leetcode за свързани елементи от списъка

Подход (рекурсивен)

Можем рекурсивно да извикаме същата функция, за да върнем главата на необходимия списък. Постигаме това, като извикваме функцията на следващите суфикси на дадения списък с някои условия. Трябва обаче да се справим с основния случай, когато списъкът е празен. Има само един специален случай:

Ако главата на списъка има стойност, равна на val (вход), след това трябва да върнем функцията, извикана на следващия й възел. Това се прави, за да се избегне добавянето на текущия възел към предишните възли на списъка (тъй като функционалният стек е завършен).

Прилагане на решение за премахване на свързани елементи от списъка Leetcode Solution

Програма 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

Анализ на сложността на решението за допълнение на номера с Leetcode

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

НА), където N = дължината на списъка. Посещаваме всеки елемент само веднъж в най-лошия случай.

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

O (1). Както следва кода рекурсия на опашката.

Подход (итеративен)

За да изтрием който и да е възел, трябва да имаме адреса на предишния му възел, за да можем да направим предишната точка към следващия. Това дава идея да се поддържа a предишен указател, който ще ни помогне да манипулираме указатели в списъка. Сега важният момент е, че първият възел в списъка няма предишен възел. И така, трябва да добавим контролен възел в началото на списъка. Сега можем да преминем през първия възел в списъка (възел до дозорния възел) и ще се изправим пред следните две условия:

1.) node-> value == val: В този случай ще зададем prev-> next = node-> next. Това ще свърже предишния от текущия възел със следващия от текущия възел и ще изтрие текущия възел, като използва: изтриване (currentNode)

2.) В противен случай просто задаваме prev = глава за предстоящи възли.

Накрая следващият от страж е задължителният списък.

Прилагане на решение за премахване на свързани елементи от списъка Leetcode Solution

Програма 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

Анализ на сложността на решението за премахване на свързани елементи от списъка Leetcode

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

НА), тъй като повтаряме целия списък веднъж. N = дължина на списъка

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

O (1), тъй като ние само постоянно пространство в паметта.