Удаление элементов связанного списка Leetcode Solution  


Сложный уровень Легко
Часто спрашивают в саман Амазонка Apple Bloomberg Capital One Facebook Google Microsoft
алгоритмы кодирование Интервью подготовка к собеседованию LeetCode LeetCodeSolutions Связанный список Чистое хранилище

Постановка задачи  

В этой задаче нам дается связанный список с его узлами, имеющими целочисленные значения. Нам нужно удалить из списка некоторые узлы, которые имеют значение, равное вал. Проблема не требует решения на месте но мы обсудим один такой подход.

Пример

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

Удаление элементов связанного списка Leetcode Solutionшпилька  

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

Мы можем рекурсивно вызвать ту же функцию, чтобы вернуть заголовок требуемого списка. Мы достигаем этого, вызывая функцию для последующих суффиксов данного списка с некоторыми условиями. Однако нам нужно обработать базовый случай, когда список пуст. Есть только один особый случай:

Если заголовок списка имеет значение, равное val (ввод), затем нам нужно вернуть функцию, вызванную на ее следующем узле. Это сделано для того, чтобы текущий узел не добавлялся к предыдущим узлам списка (по мере завершения стека функций).

Реализация решения 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

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

Сложность времени

НА), где N = длина списка. Мы посещаем каждый элемент только один раз в худшем случае.

Смотрите также
Заливка LeetCode

Космическая сложность 

O (1). Как следует из кода хвостовая рекурсия.

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

Чтобы удалить любой узел, нам нужен адрес его предыдущего узла, чтобы мы могли сделать предыдущую точку следующей. Это дает идею поддерживать предыдущий указатель, который поможет нам управлять указателями в списке. Теперь важным моментом является то, что первый узел в списке не имеет предыдущего узла. Итак, нам нужно добавить сторожевой узел в начало списка. Теперь мы можем пройти через первый узел в списке (узел рядом со сторожевым узлом) и столкнемся со следующими двумя условиями:

1.) node-> value == val: в этом случае мы установим предыдущая-> следующая = узел-> следующая. Это соединит предыдущий из текущего узла со следующим из текущего узла и удалит текущий узел, используя: удалить (currentNode)

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

В конце концов, следующий дозорный - это требуемый список.

Реализация решения 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) {
    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 Solution

Сложность времени

НА), поскольку мы перебираем весь список один раз. N = длина списка

Смотрите также
Решение Leetcode для объединения отсортированных массивов

Космическая сложность 

O (1), так как у нас только постоянная память.

1